Metakit 2.3.2 beta June 29, 2000
Welcome to the latest release of the Metakit embedded database library. This is the first beta release, it is functionally 99% done, but some problems/bugs still remain. Please stick with MK 2.01 for production.
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 - the Tcl language binding now includes a command-object API - 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 release 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, and since this a first beta: 2.3.2 ...
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.
There is a known bug in this 2.3.2 beta, which can mess up free space use after the commit which performed the conversion. To avoid the problem, you should open the old file, commit to force conversion, and then first close and re-open the file. This problem will be resolved before final.
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.
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).
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:
https://www.equi4.com/previews/mk4api.bin
and one of the following (sorry, only Linux and Windows for now):
https://www.equi4.com/previews/tclkit-linux.bin
https://www.equi4.com/previews/tclkit.exeUncompress 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").
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.2 beta passes all but one of the original regression tests (the one which does not pass is related to serialized data loading).
There is a known bug when converting files on the fly, as noted before.
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.
A recent change appears to have re-introduced a few memory leaks.
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.
Apart from the above, MK 2.3.2 beta already appears to be quite solid. There have been several releases of Tclkit based on it, and these have been tried with a number of active projects without major problems.
That is why the code is now being released as beta. Please give it a whirl and let me know how it goes. Depending on your feedback, I can then start to define a release time schedule.
-- Coen Siegerink <[email protected]>