Metakit 2.3.4 - last release candidate March, 2001
Welcome to the latest release of the Metakit embedded database library.
This is a near-final release, it is functionally 100% done, but a few minor
problems/bugs still remain. Release MK 2.3.4 is essentialy ready for
production use, with one extremely important disclaimer:
>>> Do *not* rely on new commit-aside/-extend models, these
>>> new features are not good enough for general use yet.
>>> Worse still, they will remain experimental in 2.3 final!
This document describes the main changes since 2.01 in some detail:
- a new version numbering scheme (again)
- some essential file format changes
- new commit modes: commit-aside and commit-extend
- the memo datatype has been removed from the public API
- made a start with making custom viewers modifiable
- new "mapped views": hashed, blocked, and ordered
- recursive view definitions
- the Tcl language binding now includes a command-object API
- better error checking to avoid disk full errors from being missed
- documentation and current status
Most of these changes are intended to make Metakit more scalable and to
improve performance in various ways. This process is not complete, as
several new bottlenecks have been intoduced in the new code. The main goal
of the 2.3 release is to make sure the file format is correct and
functioning properly. The next minor releases will then address various
bottlenecks to take maximum advantage of the new file format.
See the last section for notes about the status and stability of MK.
NEW VERSION NUMBERING SCHEME
I am adopting a more rigid 3-level numbering scheme, as follows:
- stable release are X.0, X.2, X.4, i.e. even-numbered
- development releases are X.1, X.3, X.5, i.e. odd-numbered
- alpha releases are all called X.Y.1, they are distinguished only by
the date embedded in the snapshot tarball, e.g "mk2-20000629.tar.gz"
- beta releases are all called X.Y.2, again only dates in snapshots
- the "final release candidate" will be called X.Y.3, with one extra
chance to fix any remaining mistakes in a release called X.Y.4
- the first final release will be called X.Y.5, with every new update
and fix incrementing that third digit
To avoid confusion between 2.01 and a version number of 2.1, this new
release has been dubbed 2.3 - since it is still development version.
NEW FILE FORMAT
This release has major changes in the way data is stored on file, or to be
more accurate: the data itself is hardly different, but administration of
the data is now radically different (it used to be a tree-walk on each open
and commit, the new format reads/commits far more lazily).
The most immediate effect is that file opens are now O(1), and no longer
take time proprotional to the number of subviews and columns. There has
been some "cutting corners" in this release, but the file format is now
able to support several degrees of laziness, which will gradually be
implemented to make opens instant, and frequent commits cheap.
The biggest drawback of this change, is that there are now two different
file formats. The new 2.3 release will convert old formats on-the-fly
during open, and will save the new format on commit. This means that
moving to the new release is relatively painless, but once changes are
committed with 2.3, you can not go back to 2.01 or earlier.
The "random" versus "serial" file format differences of pre-2.3 Metakit is
now gone. When serializing data out with "SaveTo", MK will now figure out
how to save the file in an optimally compact form, suitable for loading on
demand. That means that the best way to reorganize a MK datafile to get
rid of internal free space, is now to serialize it out to file. As extra
benefit, a serialized file has an accurate file size in the header, so that
the exact size is known up front when serializing back in. This can be
useful when data is streamed across a communications channel. Finally,
storage objects are now derived from views, and both can be initialized
from an input file/stream.
One special file format change affects the top level: MK datafiles are now
conformant with *IFF file formats (i.e. 8-byte header with type and size).
Serialized files, and files using the ordinary ("full") commits consist of
exactly one section. However, files using commit-extend (described below)
will contain multiple sections.
The new file format now uses a tail marker. Because of that, a datafile
can be appended to another file. MK will always start by looking for the
tail marker to determine where the file starts (resorting to old-style
search-from-start to deal with pre-2.3 files). Another effect, is that any
existing file can now be opened by MK. If there is no valid MK data, new
contents will be appended. There is a new c4_Strategy::EndOfData member
which returns -1 if the file contained to valid MK data. One goal of all
this logic, was to allow adding MK data at the end of executables.
Several features have been prepared for in the new file format, including
heterogenous views, clustering, compression, encryption - as well as the
ability to store revisions. None of this is anywhere near implementation,
so please don't expect much in these areas for quite some time. The main
reason to mention this at all, is to indicate that the new file format has
plenty of room for future expansion.
NEW COMMIT MODES
There are two new commit modes: "commit-aside" and "commit-extend", with
very different characteristics. They cannot yet be combined, but this is
one of the goals, since that will support some interesting scenario's.
Commit-aside stores all changes made to one datafile in another one. The
primary datafile is not altered, it may be opened read-only. The changes
are saved in a special format and managed completely by MK. Opening the
original file later will of course lead to the original pre-commit state.
By attaching that other file (using c4_Storage::SetAside), the latest
changes become visible again. This logic can be stacked, though the API
for all this is not very intuitive. Commit-aside applies to every change
made to the file, including structure changes. The second data file is in
effect a "difference file", it has no use without the original file.
In commit-aside mode, the c4_View::Commit call takes an extra argument,
specifying whether to do a "fast" or a "full" commit (fast is default).
Fast means: save the changes in the aside file, full means: apply all
changes to the primary datafile and clear the aside file contents. The
rollback also comes in two versions: fast rollback rolls back to the state
before the last commit, while full rollback forgets about commit aside
altogether and reverts to the original datafile (without deleting the aside
file contents - it can be re-attached later). Note that any changes made
to the primary datafile will invalidate the aside file.
The purpose of commit-aside is two-fold: to speed up commits, and as a way
to save changes when a key database needs to remain unchanged (this is
useful when distributing over CD-ROM, or to manage original releases, for
example). Commit aside is not yet optimally efficient, but it'll get
better - the key issue is that the amount of data saved is proportional to
the amount of change, and *not* to the size/number of views & columns,
Commit-extend is somewhat different: it is a modified version of a normal
commit, which saves all changes at the end of the datafile, in such a way
that current readers are not affected. Readers will not see any changes
until they do a rollback (which is a misnomer in this context). At that
point, the reader will resynchronize to the latest *committed* changes.
Commit-extend supports multiple readers and a single writer, and due to the
way it is implemented it does so without any locking or contention. The
trade-off is that datafiles will grow on each commit, and need to be
cleaned up periodically to avoid filling the disk. This can often be
scheduled to some "idle" period, at which point a normal (exclusive) open
and commit can be performed, possible followed by serialization to generate
an optimally-packed datafile again. Note that commit-extend is not much
more efficient than a normal commit, it still writes out entire changed
columns (there is a speedup because free-space is not reclaimed).
In this release, commit-aside and commit-extend cannot be combined: this
would greatly reduce the amount of data saved on commit, while supporting a
form of high-performance concurrency. This "hybrid commit" is planned for
the final 2.3 release, as is a more sophisticated degree of delta- storage
in commit-aside.
NO MORE MEMOS TO WORRY ABOUT
The memo ("M") datatype has always been a confusing addition to MK, since
it complements the bytes ("B") datatype yet adds very little value. It has
always been difficult to decide between B and M in the design phase, and
since there were no conversion tools - that choice has to be made up front.
This release does away with memos.
At least, that's how it looks on the outside. On the inside, MK has now
been extended to dynamically switch between column-wise (B) and item-wise
(M) storage, depending on the amount of data and the size of the view. The
result is likely to be better than either approach before, because the
choise is based on actual dynamics, and on an item-by-item basis. The
heuristics which determine how data is stored internally are still being
tweaked. But the good news is that binary data storage is now always
specified in a uniform manner, i.e. through c4_BytesProp. In a way, this
is analogous to how MK has always offered "adaptive integers", i.e. the
fully transparent switch between 1/2/4/8/16/32-bit integers.
Another change is that strings are now internally based on the same more
adaptive style, they now scale much better than before and also no longer
suffer from a startup delay (caused by a pre-2.3 null-byte scan on open).
MODIFIABLE CUSTOM VIEWERS
Custom viewers were introduced in version 1.8 and have turned out to be
extremely effective and flexible. Almost all the relational operators of
MK are implemented as classes derived from c4_CustomViewer. As of this
release, custom viewers now support the ability to handle modifications.
Many of the existing viewers, such as join and intersection, are still
read-only (and some changes could never be handled properly), but a few
others were realtively easy to extend. View operators such as Concat,
RemapWith, Pair, now support modifications on the resulting view. These
modifications are passed back to the underlying views.
There are several types of modifications: setting individual properties in
individual rows, inserting/removing rows, and changing structure.
Propagating individual property changes is usually easiest to implement.
Inserting/deleting rows is far more complex, and not even semantically
obvious in many cases (where do you insert row N, if the view is the result
of concatenating an N-row view A and an M-row view B?). For the moment,
row insertions/deletions are only implemented in mapped views (see below).
The last category of changes is the most complex of all, and has not been
addressed in this release. The best way to stay out of trouble is to only
restructure views on open (i.e. at app initialization time), and to then
only deal with inserting/modifying/deleting rows. Subviews are no
different, and can be modified in the same way as the main views.
MAPPED VIEWS
Modifiable custom viewers which support row insertion and deletion have
been dubbed "mapped views", because they usually represent a mapping of
some kind over one or more underlying views. Changes are propagated to the
underlying views in the way that is deemed most intuitive.
The 2.3 release contains three new mapped view implementations: hash,
blocked, and ordered.
The hash view takes a main "data" view as input, plus a "map" view. The
map view must be defined with a fixed structure ("_H:I,_R:I"), and is
managed fully by the hash view. The data view can be any structure, it is
the collection of data on which hashing is to be applied. When hash views
are defined, they must be told how many of the first properties form a key
(note that the key fields must always be first). What the hash view does
is create a new layer on top of the original data view, which intercepts
all modification and find requests. Modifications are applied to the data,
but also cause the map view to be adjusted as needed. Find requests which
happen to specify a value for the key are singled out and cause a fast O(1)
hash lookup to take place.
There are several consequences of this approach: first of all, it is up to
the application to set up a hash view after open (for now at least). Also,
once you want hashing, you should *never* change the underlying data or map
views - the only way to make sure they contain the proper info for hashing
to work is to always change *through* the hash view. Note that the data
view is the same as without hashing, all details needed for instant hash
lookup are maintained in the separate map view. Unlike most conventional
hash tables, insertion by position is still allowed, though insertion at
the end is fastest (by far). Also unlike most hash implementations, it is
possible to change the key of a row, because MK will rehash whenever that
happens. Caveat: the details of changing key fields are not yet correct in
this release.
Find requests automatically detect hash views and optimize accordingly.
The "python/find.py" script demonstrates find access optimizations.
The blocked view is a view which stores its rows in "blocks", i.e. one
extra level of subviews. To make a view of the form "a:I,b:S,c:D" blocked,
you have to define it as "_B[a:I,b:S,c:D]" instead, then call the Blocked
member to produce the view you can work with. The blocked view then takes
over all insertions and deletions and rebalances both root and leaf blocks
in such a way that none of the subviews ever contains either very few nor
very many rows ("few" and "many" depend on the total number of rows,
everything is adaptive). Due to the extra level of indirection, blocked
views are slightly slower, but the gain is that they can scale to an
unlimited number of rows and still offer good performance (probably O(log
N) instead of the usual O(N)). These blocked views will behave like
ordinary views in every respect, i.e. you can iterate and access rows by
position, regardless of the blocking and occasional rebalancing that takes
place underneath.
The ordered view is a view which assumes the underlying view is sorted on
its first N properties (N defaults to 1), and which maintains that order by
ignoring isnert positions and supplying its own instead. As with hash
views, keys are unique. Inserting a row which has the same key as another
one will cause the other row to be replaced instead.
Ordered views intercept changes, but also find requests. If a find
specifies a value for the key field(s), then binary search is used to find
the rows far more quickly.
All of the above views can be combined, e.g. by layering a hash view on top
of a blocked data view, you get a persistent hash structure which scales up
indefinitely, yet offers O(1) hash access performance.
An ordered view on top a blocked view creates a blocked structure which
keeps its rows sorted. The current release will take advantage of binary
search if possible - but real btree-like searches will be implemented
before 2.3 final (this is far more efficient than "just" binary search, due
to its much higher locality of reference).
And finally, you can layer an ordered view on a hash view on one or two
blocked views (for data and/or map). This creates a structure which
maintains sort order (and can be traversed in that order), yet with instant
hash access on single key values. The "tcl/mapped.tcl" script shows an
example of various ways in which this can be done.
RECURSIVE VIEW DEFINIONS
You can now define views with recursive subviews. The way this is done is
to specify a subview of the form "subview[^]". An example:
roots[name:S,children[^]] This define a "roots" view containing 0
or more rows. Each has the form given above, which is also identical to:
name:S,children[name:S,children[^]] In other words, the "children"
subview has the same format as its parent, and this continues to arbitrary
depths. The above example is in fact nothing but a definition of a tree
containing named nodes. Restructuring works, it will recursively
restructure the entire tree.
COMMAND OBJECTS IN MK4TCL
The Mk4tcl extension has undergone a massive face-lift. The original API
is still there, but there is now also an OO-style command interface (in the
same way as Tk works). This is based on work by Matt Newman. Because of
this, a far more powerful binding to the MK C++ core is now available from
Tcl (as it has been in Python for a while). These new calls include
relational operators, such as join, select, sort, etc. For now, this is
"thinly" documented in the "tcl/mk4tcl.h" header. Another useful source to
check, is the "tcl/test/mk5object.tcl" script.
The Tequila server and the I/O handler package (iohan) have undergone some
changes (extensions, really).
BETTER ERROR CHECKING
The write and commit logic have been improved to better detect whether
anything went wrong during the commit, to prevent the final end marker from
being updated. This has the effect of ignoring all changes. The most
important change was to check and remember errors in fflush, and to make
the c4_Stream::Write member return a success flag i.s.o. void.
DOCUMENTATION
Documentation. Hm, what documentation? I have converted the C++ docs to
work with Doxygen, which extracts everything from comments in the source
code. The C++ documentation is available as a scripted document. To get
it, you need to download the file:
http://www.equi4.com/previews/mk4api.bin and one of the following
(sorry, only Linux and Windows for now):
http://www.equi4.com/previews/tclkit-linux.bin
http://www.equi4.com/previews/tclkit.exe Uncompress and make all
files executable, then drop mk4api on tclkit, or whatever your explorer,
navigator, finder, or shell wants you to do. If this is not workable, I
will create a tarball of the html/gif files.
For Python and Tcl, check the pages doc/python.html and doc/tcl.html in the
source distribution (they are also part of the above "mk4api"). There is a
new examples/ directory with several Python and Tcl examples.
The documentation is far from complete ("non-existent" or "wrong" are also
applicable terms in some cases, I'm afraid). I have started work on
improving this. Comments on what needs to be done first are most
gratefully accepted - there is a huge amount of work left to do.
CURRENT STATUS
This 2.3.4 build passes all but one of the original regression tests (the
one which does not pass is related to serialized data loading).
There are several performance bottlenecks, despite the fact that the new
format really should work better than the pre-2.3 file format. For now,
the first goal is to make sure that the file format is 100% frozen and
useable as is - to avoid even more complex future conversion nightmares. I
will start aiming for top speed *after* everything works properly.
The commit logic can be slow for complex datasets, I am looking into it.
There are some problems when changing keys in hash & ordered views, the
best workaround is to not change key properties - delete and re-insert the
row instead if you need this capability.
This MK 2.3.4 final release candidate is very solid. Recent versions of
the beta preceding it have been in use in a wide range of active projects
without substantial problems. A byte-order conversion bug has recently
been found and fixed, as well as double alignment on Solaris.
At this point, I recommend using 2.3.4 as replacement for 2.01, except when
tweaks for top performance have been done in 2.01 (2.3.4 is not yet as
highly optimized, and has a slightly different performance behavior).
-- Jean-Claude Wippler <jcw@equi4.com>
