LoganBerry.mesa
Copyright © 1985 by Xerox Corporation. All rights reserved.
Doug Terry, March 6, 1986 11:11:43 am PST
LoganBerry is a simple facility for managing databases. Data is stored in one or more log files and indexed using stable btrees. This "poor man's" database facility is intended to allow various types of data to be stored persistently. 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],
Rope USING [ROPE],
RPC USING [Conversation];
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;
SchemaInfo: TYPE = RECORD[
dbName: ROPE, -- name of database schema file
keys: LIST OF AttributeType, -- available indices, the primary key is listed first
indexNames: LIST OF ROPE, -- names of index files
logs: LIST OF LogID, -- logs comprising the database
logNames: LIST OF ROPE -- names of log files
];
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.df

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

Directory [Indigo]<LoganBerry>Backups>SampleDB>
--> log 0 readwrite
Activity.log!2 12-Aug-85 12:07:24 PDT
--> log 1 readonly
Readonly.log!1 5-Aug-85 11:50:51 PDT
--> index "Name" primary Name.index
============================
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; see LupineUsersGuide.tioga for information on establishing secure conversations.
Conv: TYPE = RPC.Conversation;
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: ROPENIL];
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: BOOLEANFALSE] 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.
END.
Doug Terry August 12, 1985 11:58:15 am PDT
created
Doug Terry, October 22, 1985 11:26:03 am PDT
changes to: DIRECTORY, Cursor, OpenDB
Doug Terry, November 19, 1985 10:13:47 pm PST
changes to: BuildIndices
Doug Terry, November 20, 1985 11:31:42 am PST
changes to: DeleteEntry, BuildIndices
Doug Terry, November 26, 1985 8:16:02 pm PST
changes to: LoganBerry, ErrorCode, ReadEntry, EnumerateEntries, GenerateEntries, NextEntry, WriteEntry, DeleteEntry, Close
Doug Terry, January 20, 1986 10:44:06 am PST
changes to: Conv, Error, Open, ReadEntry, GenerateEntries, NextEntry, EndGenerate, WriteEntry, DeleteEntry, Close, BuildIndices, CompactLogs, DIRECTORY
Doug Terry, January 23, 1986 3:16:08 pm PST
changes to: Close, ErrorCode, Open, ReadEntry, EnumerateEntries, NextEntry, WriteEntry, DeleteEntry
Doug Terry, February 26, 1986 6:23:04 pm PST
changes to: Open
Doug Terry, February 27, 1986 7:42:44 pm PST
changes to: ErrorCode changed to be ATOMs rather than an enumerated type.
Doug Terry, February 28, 1986 4:37:47 pm PST
changes to: WriteEntry so that atomic replacement of complete entries is possible.
Doug Terry, March 5, 1986 4:54:59 pm PST
changes to: SchemaInfo, Describe was introduced so that clients, e.g. the browser, can obtain information about the database schema.
Doug Terry, March 6, 1986 11:11:43 am PST
changes to: ErrorCode, WriteEntry