LT.  KERNAL MULTIUSER DATABASE PROGRAMMING

by: BigDumbDinosaur


PROLOGUE

Elsewhere on this site, it is possible to download a series of articles describing how to use the Lt. Kernal's keyed random access facilities.  I originally wrote those articles in late 1988 to help a fellow Commodore programmer understand aspects of the Lt. Kernal disk operating system (LK DOS) that were out of reach from BASIC.  At the time, the information in these articles represented nearly a year's worth of experimenting and code development.  Eventually I sent edited copies to Fiscal Information Inc. for inclusion in the "Power Station" series of articles that were published for public use.

Keyed random access is one of the many distinguishing features of the LK DOS.  Lt. Kernal developers Lloyd Sponenburgh and Roy Southwick apparently got the idea for it from the polyfile database engine that was an operating system feature of the Point 4 minicomputer systems sold by Fiscal in the 1980's.  Polyfiles were similar in some ways to the ISAM (Indexed Sequential Access Method) database architecture that was invented at IBM, and which continues to be widely implemented in modern databases.  The Lt. Kernal does not have polyfile or native ISAM capabilities, but by joining a keyed index file to a relative file-like structure, ISAM-like database management can be implemented with user-written code.

An ISAM database involves the use of two files.  One file, the data file, contains fixed length records built from fixed length fields, and is addressed by logical record number in a manner similar to that of a Commodore relative file.  The other file, the index, contains lexically sorted record keys associated with record pointers.  The retrieval of any given record is achieved by searching the index for the matching key.  Assuming that the key exists, the record pointer will be returned to the calling program, which can then use it to position to the right spot in the data file and load the record into workspace.

A fundamental feature of ISAM is that keys are actually derived from the records themselves and are not explicitly specified when a new record is written.  At the time of the creation of the ISAM database, information will be provided that tells the database engine where in the record to look for the key field(s).  When a new record is written the database engine will create a key from the specified fields and automatically attempt to insert that key into the index, as well as write the record into the data file.  In the event the record has the same key as an existing record the new record will replace the old, unless the database engine is told not to do so.

ISAM allows the use of multiple sorts, which are the ways in which keys are organized (sorts are called directories in Lt. Kernal keyed index files—I will use the term "sort" so as to avoid confusion with a disk directory).  In every ISAM database, there is a primary sort, which is organized from unique keys.  For example, in a customer master database, the customer's name could be the primary sort.  In many cases, additional sorts, called secondary sorts, are implemented to allow the retrieval of records using some criteria other than the primary sort key.  For example, in a customer master database, the customer's telephone number could be a secondary sort key, allowing the lookup of a customer by entering his phone number or by using his name (program context usually figures out which sort to use based upon the information entered by the user).

ISAM databases have a finite capacity that is determined by the environment in which they are created and maintained.  The limitations encountered in the Lt. Kernal environment are primarily the result of the 16 bit addressing scheme used throughout the LK DOS.  Therefore, the maximum record number that can be associated with an ISAM database would be 65,535 ((2^16)-1), which is also a limitation imposed by the key file processor (which associates a 16 bit pointer with each key).  The limit on file size is a function of maximum logical unit (LU) size, again governed by the use of 16 bit pointer arithmetic, resulting in a maximal LU size of 33,554,432 bytes or 32 megabytes (512 * 2^16).  The keyed index file processor imposes file size limits of its own: again, 16 bit addressing limits any one sort to 65,535 keys, as long as the key size is less than 14 bytes.  As the key size increases beyond 13, the maximum number of keys will decrease, bottoming out at 6750 with a maximum key size of 30 bytes.  A final limitation is the maximum record size of 3583 bytes.  All of these limits are practicable in situations where usage of the Lt. Kernal might be appropriate.

The concurrent access database methods described in the "Power Station" articles do not implement ISAM, as they address records by disk block logical number and byte position within a block, and do not extract record keys from the records themselves.  Also, the block and position method of record access described therein has the limitation of modest record sizes (510 byes maximum), with minimal choices of record sizes, as well as the need to associate a 24 bit pointer with each key, 16 bits for the disk block logical number and 8 bits for the byte position value.  At the time when I was developing the software that used this method, I was primarily concerned with getting a working system up and running as soon as possible, which meant the block and position method was a matter of expediency, not exemplary programming practice.  Later on, I worked out the code needed to implement an ISAM-like environment, but for a variety of reasons, never published it.

In order to support any kind of an ISAM-like database, the data file has to be addressable by a zero-based, logical record number and it has to be possible to use any desired record size up to whatever maximum is imposed by the database engine.  Reading and writing arbitrarily sized records gives rise to complications in attempting to prevent damaging simultaneous writes.  It is no longer sufficient to lock a block, as the record may well span over several blocks, none of which can be disturbed until control of the record is relinquished.  Therefore, the locking methodology described in the "Power Station" articles would have to be changed in order to control concurrent access to individual records.

You might be thinking at this point, "Why not use a relative file?"  Fiscal did not provide any means for preventing simultaneous writes to Lt. Kernal data structures, including the block allocation map and directory of an LU (which is why simultaneous writes to an LU are usually fatal).  The relative file structure is particularly vulnerable to damage from simultaneous writes, as portions of the file are buffered in host adapter memory and are not flushed until a new position command is received.  Therefore, it is impossible to protect a relative file from simultaneous writes by any means.  The only solution is to replace the native relative file structure with something that can be adequately protected.

As will be seen later on, all of this will be possible by building upon the methods described in the "Power Station" articles.

Copyright ©1988-2007 by BCS Technology Limited.  All rights reserved.