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.
|