LoganBerry.mesa
Copyright Ó 1985, 1992 by Xerox Corporation. All rights reserved.
Doug Terry, July 26, 1990 1:42 pm PDT
Brian Oki, March 30, 1990 11:55 am PST
Willie-s, April 23, 1992 2:59 pm PDT
LoganBerry is a simple facility that allows various types of data to be stored persistently. Data is stored in one or more log files and indexed using stable btrees. A database survives processor crashes, but the data management facility does not provide atomic transactions. Only very simple queries are supported: retrieval by key or key subrange. Databases may be shared by multiple clients and accessed remotely via RPC.
DIRECTORY
RefID USING [ID, nullID],
Rope USING [ROPE];
LoganBerry: CEDAR DEFINITIONS
~ BEGIN
ROPE: TYPE ~ Rope.ROPE;
Data representation
The database is maintained as a collection of entries, where each entry is a set of type:value attributes. Both the type and value of an attribute are simply text strings (i.e. ROPEs). However, the programmer interface treats attribute types as ATOMs. For instance, a database entry pertaining to a person might be [$name: "Doug Terry", $phone number: "494-4427", $workstation: "Lake Champlain"].
AttributeType: TYPE = ATOM;
AttributeValue: TYPE = ROPE;
Attribute: TYPE = RECORD[
type: AttributeType,
value: AttributeValue
];
Entry: TYPE = LIST OF Attribute;
Database entries are stored in a collection of logs. A database is updated by appending an entry to the end of a log, log entries are never overwritten (except when a log is compacted or replaced in its entirety). Updating individual attributes of an entry requires rewriting the complete entry. In many cases, all of the logs are readonly except for a single activity log. All updates are applied to the activity log unless the client explicitly controls which logs are written.
LogID: TYPE = [0..255];
activityLog: LogID = FIRST[LogID]; -- default log for updates
Access methods
Only key-based access methods are supported on a database. These are provided by btrees. A separate btree index exists for each attribute type that serves as a key for the database.
A sequence of database entries, sorted in btree order, can be accessed using either an enumerator or generator style of retrieval. Generators employ a cursor to indicate a logical position in the sequence being retrieved. A cursor can be used to traverse a sequence in increasing or decreasing order.
Cursor: TYPE = RefID.ID;
CursorDirection: TYPE = {increasing, decreasing};
Database schema
A database must be "opened" before any of its data can be accessed. The Open operation reads a database schema, which contains information about all logs and indices that comprise a database, and returns a handle that identifies the database in subsequent operations.
OpenDB: TYPE = RefID.ID;
nullDB: OpenDB = RefID.nullID;
LogInfo: TYPE ~ REF LogInfoRec;
LogInfoRec: TYPE ~ RECORD[
id: LogID, -- log number
file: ROPE -- name of log file
];
IndexInfo: TYPE ~ REF IndexInfoRec;
IndexInfoRec: TYPE ~ RECORD[
key: AttributeType, -- index key
file: ROPE, -- name of index file
order: ATOM ¬ $lex -- ordering of index, e.g. $lex, $ascii, $gmt, $int
];
SchemaInfo: TYPE = REF SchemaInfoRec;
SchemaInfoRec: TYPE = RECORD[
dbName: ROPE, -- name of database schema file
logs: LIST OF LogInfo, -- logs comprising the database
indices: LIST OF IndexInfo -- available indices, the primary key is listed first
];
A schema is created by clients of this package and stored in a DF file that can be used to backup the database. Lines of the file starting with "-->" are deemed to contain schema information for the file named in the subsequent line of the DF file or at the end of the same line. The two types of schema entries are as follows:
--> log <logID> <readOnly or readWrite> <optional CR> <filename>
--> index <key> <primary or secondary> <optional CR> <filename>
The following is a sample database schema file:
============================
-- SampleDB.lbdf

Directory [Indigo]<LoganBerry>Backups>Top>
SampleDB.lbdf!3 12-Aug-85 13:16:12 PDT

Directory [Indigo]<LoganBerry>Backups>SampleDB>
--> log 0 readwrite
Activity.lblog!2 12-Aug-85 12:07:24 PDT
--> log 1 readonly
Readonly.lblog!1 5-Aug-85 11:50:51 PDT
--> index "Name" primary Name.lbindex
============================
Basic operations
All of these operations (except EnumerateEntries) can be invoked via RPC. They take a RPC conversation as the first argument so that secure remote procedure calls can be made to a LoganBerry database server.
Conv: TYPE = REF;
Errors raised during the execution of an operation indicate uncommon or abnormal conditions. Clients should be prepared to catch these.
Error: ERROR [ec: ErrorCode, explanation: ROPE ¬ NIL];
ErrorCode: TYPE = ATOM;
The possible ErrorCodes are:
$BadSchema, -- the schema can not be parsed
$CantOpenSchema, -- the schema file could not be opened
$BadDBHandle, -- an invalid OpenDB handle was passed to some routine
$BadCursor, -- an invalid cursor was passed to some routine
$NoIndex, -- the key presented in a read or delete operation has no associated index
$NoPrimaryKey, -- a new entry being written does not contain a primary key
$ValueNotUnique, -- a new entry being written contains the same primary key value as an existing entry, or the value supplied for a delete does not uniquely specifiy an entry
$CantOpenLog, -- a log file could not be opened
$BadLogEntry, -- a log entry is of the wrong format
$LogReadOnly, -- the specified log can not be updated
$InvalidReplace, -- an entry being replaced is in a different log than its replacement
$CantOpenIndex, -- a btree file could not be opened
$BadIndex, -- a btree index is corrupted
$DBClosed, -- the database has been closed
$DBNotAvailable, -- the database has been taken out of general service
$InternalError -- indicates some miscellaneous internal error
Open: PROC [conv: Conv ¬ NIL, dbName: ROPE] RETURNS [db: OpenDB];
Initiates database activity and checks for consistency. This can be called any number of times to get a new OpenDB handle or reopen a database that has been closed. Indices are automatically rebuilt if any are missing or if a partially-completed update left them out-of-date.
Errors: CantOpenSchema, BadSchema, CantOpenLog, BadIndex
Describe: PROC [conv: Conv ¬ NIL, db: OpenDB] RETURNS [info: SchemaInfo];
Returns schema information about the database.
Errors: BadDBHandle
ReadEntry: PROC [conv: Conv ¬ NIL, db: OpenDB, key: AttributeType, value: AttributeValue] RETURNS [entry: Entry, others: BOOLEAN];
Returns an entry that contains the given attribute value for the given key; returns NIL if none exists. If the key refers to the primary index then the unique entry is returned and `others' is FALSE. If the key is secondary and several entries exist with the same value for the key, then an arbitrary entry is returned and `others' is set to TRUE; use EnumerateEntries to get all of the matching entries.
Errors: BadDBHandle, NoIndex, DBClosed, BadIndex, BadLogEntry
EntryProc: TYPE = PROC [entry: Entry] RETURNS [continue: BOOL];
EnumerateEntries: PROC [db: OpenDB, key: AttributeType, start: AttributeValue ¬ NIL, end: AttributeValue ¬ NIL, proc: EntryProc] RETURNS [];
Calls `proc' for each entry in the specified range of key values. The enumeration is halted when either the range of entries is exhausted or `proc' returns FALSE. A NIL value for `start' represents the least attribute value, while a NIL value for `end' represents the largest attribute value. Thus, the complete database can be enumerated by specifying start=NIL and end=NIL with `key' equal to the primary key.
WARNING: THIS ROUTINE CAN NOT BE USED ACROSS AN RPC CONNECTION; USE GenerateEntries INSTEAD.
Errors: BadDBHandle, NoIndex, DBClosed, BadIndex, BadLogEntry
GenerateEntries: PROC [conv: Conv ¬ NIL, db: OpenDB, key: AttributeType, start: AttributeValue ¬ NIL, end: AttributeValue ¬ NIL] RETURNS [cursor: Cursor];
Similar to EnumerateEntries, but creates a cursor so that entries in the specified range of key values can be retrieved using NextEntry (defined below). Initially, the cursor points to the start of the sequence. A NIL value for `start' represents the least attribute value, while a NIL value for `end' represents the largest attribute value. Thus, the complete database can be enumerated by specifying start=NIL and end=NIL with `key' equal to the primary key.
Errors: BadDBHandle, NoIndex
NextEntry: PROC [conv: Conv ¬ NIL, cursor: Cursor, dir: CursorDirection ¬ increasing] RETURNS [entry: Entry];
Retrieves the next entry relative to the given cursor. The cursor, and thus the sequence of desired entries, must have been previously created by a call to GenerateEntries. The cursor is automatically updated so that NextEntry may be repeatedly called to enumerate entries. NIL is returned if the cursor is at the end of the sequence and dir=increasing or at the start of the sequence and dir=decreasing.
Errors: BadCursor, DBClosed, BadIndex, BadLogEntry
EndGenerate: PROC [conv: Conv ¬ NIL, cursor: Cursor] RETURNS [];
Releases the cursor; no further operations may be performed using the given cursor. This must be called once for every call to GenerateEntries.
WriteEntry: PROC [conv: Conv ¬ NIL, db: OpenDB, entry: Entry, log: LogID ¬ activityLog, replace: BOOLEAN ¬ FALSE] RETURNS [];
Adds a new entry to the database. The entry is added to the activity log unless another log is explicitly requested. The entry must have an attribute for the primary key. The primary attribute value must be unique throughout the database unless replace=TRUE; in this case, an existing entry with the same primary attribute value is atomically replaced with the new entry (both must reside in the same log).
Errors: BadDBHandle, NoPrimaryKey, ValueNotUnique, LogReadOnly, InvalidReplace, DBClosed, BadIndex
DeleteEntry: PROC [conv: Conv ¬ NIL, db: OpenDB, key: AttributeType, value: AttributeValue] RETURNS [];
Deletes the entry that contains the given attribute value for the given key. If the key is for a secondary index and the value is not unique then an Error[ValueNotUnique] is raised. Deletes are actually performed by logging the delete request (so that the log can be replayed at a later time) and then updating all of the indices.
Errors: BadDBHandle, NoIndex, DBClosed, BadIndex, ValueNotUnique, LogReadOnly, BadLogEntry
Close: PROC [conv: Conv ¬ NIL, db: OpenDB] RETURNS [];
Terminates database activity and closes all log and index files. Databases are always maintained consistently on disk so it doesn't hurt to leave a database open. The main reason for calling Close is to release the FS locks on the log files so they can be manually edited.
WARNING: THIS SHOULD NOT BE CALLED IF THE DATABASE IS BEING SHARED BY MULTIPLE CLIENTS.
Errors: BadDBHandle
Maintenance operations
An important feature of the btree-log design is: the log is the truth! Thus, the database facility need only worry about maintaining a consistent set of logs in the presence of processor crashes. Logs are fully contained. In the event of inconsistencies arising between the logs and their indices, the associated btrees can be easily rebuilt by reading the logs.
BuildIndices: PROC [conv: Conv ¬ NIL, db: OpenDB] RETURNS [];
Rebuilds the indices by scanning the logs and performing WriteEntry or DeleteEntry operations.
CompactLogs: PROC [conv: Conv ¬ NIL, db: OpenDB] RETURNS [];
Removes deleted entries from the logs by enumerating the primary index and writing new logs.
Advanced operations
Miscellaneous routines for use by sophisticated LoganBerry clients.
WriteProc: TYPE = PROC[db: LoganBerry.OpenDB, entry: LoganBerry.Entry, ident: ATOM, clientData: REF];
RegisterWriteProc: PROC [proc: WriteProc, db: LoganBerry.OpenDB, ident: ATOM, clientData: REF];
The proc will be called whenever a write or delete operation is issued to db. This information is retained over close and reopen operations, so it need be called only once per session. ident should be unique per usage of this facility; subsequent registrations with the same ident will supercede earlier ones.
UnregisterWriteProc: PROC [db: LoganBerry.OpenDB, ident: ATOM];
There is no further interest in this registration.
IsLocal: PROC [db: LoganBerry.OpenDB] RETURNS [BOOL];
TRUE iff the db is being managed directly on this host.
StartTransaction: PROC [db: LoganBerry.OpenDB, wantAtomic: BOOLEAN ¬ FALSE];
Tells LoganBerry that a sequence of update operations, i.e. a transaction, is being performed. If wantAtomic=TRUE then all operations until the next EndTransaction operation should be executed as an atomic transaction. If wantAtomic=FALSE then the outcome of subsequent operations is undefined if a crash occurs before the EndTransaction operation; this can significantly improve the performance for a sequence of update operations. This should only be called if the database is being accessed by a single client.
EndTransaction: PROC [db: LoganBerry.OpenDB, commit: BOOLEAN ¬ TRUE] RETURNS [committed: BOOLEAN];
Completes a sequence of update operations. If commit=TRUE then all operations since the last StartTransaction operation are completed; otherwise some or all may be aborted. Returns TRUE if all operations are successfully committed.
FlushDBCache: PROC [db: LoganBerry.OpenDB ¬ LoganBerry.nullDB];
Causes LoganBerry to flush all cached information about the specific database, or about all databases if db=nullDB. This may be necessary if the schema has changed, for instance.
END.