Semantics of the Library 2000 Network Storage Service
Version of March 9, 1993
(Notes from meetings and discussion attended by Mitchell Charity,
Quinton Zondervan, Manish Mazumdar, Rob Miller, Thomas Lee, Win
Treese, Ron Weiss, and J. H. Saltzer. This note also captures ideas
developed in earlier discussions with Jim Miller.)
This is a plan for a network service designed for library data.
Library data is is characterized as being large in quantity,
accumulating but not frequently changing, and long-lasting. The
service holds records that are used by three kinds of network clients:
- clients interested primarly in reading the data
- clients that maintain (update and add to) the data
- clients that maintain indexes of the data
The third kind of client provides indexing services for other clients
of the data held by the storage service; the storage service caters to
indexing clients by offering a "what's new" interface, which reports
changes. The storage service semantics include an atomic transaction
interface, both to allow an updating client to add or update multiple
records and to allow an indexing client to identify what has changed.
The storage service does not prevent deadlock, but it provides the
ability for updating clients to avoid it. The storage service
semantics are designed to minimize the amount of per-client state
maintained between client operations, with the goal of simplifying
recovery following service, client, or network failure. The storage
service semantics are also designed to not require that the service
depend for its correctness on any other service, on responses from the
client, or on correctness of any client. (Except, of course, that the
data content of the service does depend on updating clients delivering
correct data to the service.)
Some assumptions about things not yet defined:
A. Each client's identity is accurately known to the service, for
example by virtue of the client presenting a Kerberos ticket. The
semantics of that presentation are not yet defined. There are
separate access control lists for reading, adding new records and
modifying existing records, and use of the what's-new interface. The
semantics of management of these lists is not yet defined. There is
no firewall between transactions; anyone with permission to put and
modify can join in, commit, or abort any outstanding transaction.
B. The data stored is one uniquely-identified record per document.
The document record has an internal structure accessible as named
fields. The fields are:
Unique Identifier (service-chosen, not changeable)
Number of page images
Page image (repeated field)
Anchor map
Full text (format to be defined)
Text/image map (format to be defined)
Bibliographic fields--Author, title, abstract, etc. as found in
the standard bibliographic record.
A virtual field that materializes as the standard Bibliographic
record
Deduplication value
Transaction ID
All fields except Unique ID and Transaction ID are optional. Although
the structure is that of a data-base system, the only retrieval
indexes maintained by the service are for the Unique Identifier and
Transaction ID fields.
Assuming that there are many such storage services, it is not yet
clear whether the Unique ID should be unique only with respect to the
service that assigned it, and that clients are responsible for
remembering to which service to present it, or whether the service is
also responsible for making that ID unique across all such services
and that clients can somehow determine to which service to present it
by performing some operation on the ID itself.
The anchor map is a list of pairs, consisting of named anchor points
and page image indexes. Anchor points are intended to be used to
indicate where in the array of page images one can find, e.g., a table
of contents, a table of figures, the first page of chapter one, the
conclusions, or a bibliography. Anchor point names are not
interpreted by the service and not standardized; they may be provided
by a consciencious service for the convenience of browsing interfaces.
The text/image map is intended to serve two purposes: a program can
determine which page image and coordinate region of that image
contains any word listed in the full text, and a program can identify
from a coordinate region in a page image what text words lie in that
region.
The deduplication value is a bitstring derived from the initial
contents of the record, intended to uniquely distinguish it from every
other such record. The method of computing the deduplication value is
not yet defined, but it might, for example, be a 64-bit cyclic
redundancy checksum of the initial value of the bibliographic record
field. The deduplication value, once computed, is permanent; it is
not changed even if the thing it was computed from changes. Its
purpose is to allow a client to determine that references obtained
from different sources refer to the same record.
C. The service may be implemented with replicants. Interfaces for
managing replication and recovery, and guarantees about when
replicants learn about committed updates are not yet defined. The
feasibility of providing reliable replicants without making the
service depend on the service provided by the replicants has not been
established.
D. The client interested in invoking the what's-new interface does
not receive any notification that things have changed; the client is
expected to poll. Thus clients initiate all information flows either
in or out of the storage service. (Put another way, one might
implement an awareness service associated with the storage service,
but the awareness service would be a client that polls and makes use
of the what's-new interface.)
E. A document may have attachments. The method of discovering and
delivering attachments is not yet defined.
Here follow the semantics of the operations that the storage service
implements. Optional arguments are enclosed in square brackets. For
all operations the first thing returned is a status value, which may
include any of the following standard status values:
success
operation not recognized
operation not authorized to this client
invalid argument list
unknown transaction id
transaction has been aborted
transaction has been committed
as well as other status values specific to the operation.
1. Client reads data from storage service.
Operation: (Get UID List-of-Fields [Transaction-ID])
Returns: (Status Last-Transaction-ID Fields-from-Data-record)
Status: One of {Standard status values, UID not known, Data-record is a
cross-reference, Cannot reserve}
Notes: 1. Last-Transaction-ID is the last transaction that modified
the data record identified with UID.
2. The content of a Cross-reference (data-record is to be
found on a different service) needs to be defined.
3. If the client provides the optional argument
Transaction-ID, and the transaction is one currently
active, the service reserves to that transaction
the ability to modify the record. If the record is
already reserved by another transaction the service
returns the status Cannot reserve. The client can try
again, but it should be observing a discipline to avoid
deadlock. (See "deadlock avoidance," below.)
If the client provides an optional argument Transaction-ID
that is not currently active, the service returns the value
of the data in the requested record as of the time that that
transaction committed.
5. To be defined: an interface that allows negotiating the form
in which data is returned. Things to be negotiated include:
- return data via this or a different connection
- pipelining of data from successive images
- compression method for image data
- format of text
6. To be defined: the default self-identifying field
format for returned data.
2. Client opens a transaction, in anticipation of writing data.
Operation: (Open-Transaction)
Returns: (Status Transaction-ID)
Status: One of {Standard status values}
Notes: 1. Transaction-ID is assigned by the service.
3. Client writes a new data record to the service.
Operation: (Put Transaction-ID list-of-fields-and-data)
Returns: (Status, UID)
Status: One of {Standard status values}
Notes: 1. UID is the unique Id tentatively assigned by the
service for the data-record.
2. Put with fields needs to be defined.
3. The service reserves to this transaction the ability to
modify the new record.
4. Client modifies a previously existing data record.
Operation: (Modify Transaction-ID UID list-of-fields-and-data)
Returns: (Status)
Status: One of {Standard status values,
data record is reserved by another transaction}
Notes: 1. The client is expected to have previously read the
data record under the protection of this transaction, to
reserve it against change by other transactions.
5. Client commits the transaction.
Operation: (Commit Transaction-ID)
Returns: (Status)
Status: One of {Standard status values}
Notes: 1. Status value Success means that this operation
commited the transaction. Status value already committed
means that it was previously committed.
2. This is an atomic commit for all data records written
during this transaction.
6. Client aborts the transaction
Operation: (Abort Transaction-ID)
Returns: (Status)
Status: One of {Standard status values}
Notes: 1. Status value Success means that this operation
committed the transaction. Status value already
aborted means that it was previously aborted.
2. The service may unilaterally abort any outstanding
transaction, for example upon noticing that it has
been outstanding without any activity for a long time.
7. Client asks "what's new".
Operation: (What's-new From-Transaction-ID, field-list)
Returns: (Status End-Transaction-ID time-stamp UID-list)
Status: One of {Standard status value,
From-Transaction-ID too small}
Notes: 1. From-Transaction-ID too small means that the service no
longer is maintaining the log that far back.
2. If From-Transaction-ID is zero, the service returns a
complete list of all UID's in the data base.
3. Time-stamp is the date and time that
End-Transaction-ID was committed.
4. End-Transaction-ID identifies the committed transaction
immediately previous to the oldest currently
uncommitted transaction.
5. The returned UID-list is organized by transaction; it is
a precis of the log.
6. The client's field list acts a filter request; it asks that
only records for which fields in the field list changed are
included in the result. The server is not obliged to honor
this request.
8. Client asks for details on a changed record.
Operation: (What's-changed UID field-list From-Transaction-ID
End-Transaction-ID)
Returns: (Status fields-of-new-data-record fields-of-old-data-record)
Status: One of {Standard status values,
From-Transaction-ID too small}
Notes: 1. If From-Transaction-ID is zero, the returned value of
Old-data-record will be empty.
Questions: 1. Should there be an option for obtaining a diff rather
than both the old and new records?
9. Client asks for an approximate From-Transaction-ID.
Operation: (What-transaction timestamp)
Returns: (Status timestamp)
Status: One of {Standard status values, don't know}
Notes: 1. The service returns the id of the last transaction that
committed on or before the timestamp.
2. The client is intended to use this operation for
recovery, not in the normal course of activities.
Questions: 1. Is this operation really needed? It would help to
have at least one scenario in which it really helped.
Deadlock avoidance.
The client is expected to implement the following deadlock avoidance
strategy, upon receiving the status "can't reserve" on an attempt to
read with a transaction id. If the client has reserved for this
transaction any records that have a UID with a higher number than one
that can't be reserved, it must abort this transaction to release
those higher-numbered records before retrying the call to read.
Otherwise, it is free to retry the call to read, perhaps after a pause
to allow other transactions time to commit. The simplest way to
implement this strategy is to always abort the current transaction
upon receiving status "can't reserve". It is recommended that the
client begin a transaction that will involve modifying several records
by first reading all those records in UID order, to reserve them
against modification by other transactions, and also to verify that
their last-transaction values are the ones expected. Following this
recommendation will avoid the need ever to abort a transaction to
avoid deadlock.
(end)
Return to Library 2000 home page.