Context Navigation

(For more details on CowDb, please refer to the home page and the project blog.)

The COW Database (CowDb)

CowDb is a high-speed transaction object store based on Copy-On-Write technology. CowDb implements an object model based on roles, each role being built from separate classes for partness (nodes in a graph), wholeness (application logic) and relationships (references to other nodes).

COW Basics

Updates to a database built on Copy-On-Write technology are inherently atomic. All data structures are based on a tree, and no changes are comitted until the root node is written to disk. But there are a few restrictions:

A node can never be written back to the same location on disk, but must be allocated a new location.

When a node is written to a new location, the parent node which holds the location of the updated node itself needs to be updated and written to a new location.

Supporting deep virtual copies (branches) means that physically a node my have more than one parent though logically each parent has a (virtually distinct) child node. Determining when a location on disk is no longer in use then sometimes gets a tad complicated.

Disk space that has been freed must not be reallocated in the same transaction, as otherwise an incomplete transaction will result in a corrupted database.

For robustness, the root node must be the last one written to disk when a transaction completes. And on restart, you need an easy way to locate the last valid root node. CowDb reserves two areas at the beginning of the database for the root node, which are used alternately. And when written to disk, the root node carries both a checksum and a timestamp. The checksum is important for validating the root node, as the program may have been killed while writting the root node and there may have been a partial disk update. Attention to this detail makes CowDb crash proof--a graceful termination process is not required and restarting CowDb is always achieved quickly. CowDb has no recovery process and never needs one.

Graphs

You can use objects in an object store to model a graph, just as a graph can be used to model the objects in an object store. These two views become very close in CowDb, as the object model used by CowDb is "nodes in a graph." Only there are roles that the nodes can play, based on those role, various capabilities are assigned to each node. And there are different kinds of links interconnecting those nodes.

One [kind of] capability that can be assigned to a node is a map. The keys to the map are strings (names) and the values are either Nodes or node references. Nodes which are in the map are colocated on disk and are read and written when the parent node is read or written. And like a Russian doll, they can be nested to any depth.

A map can also hold handle objects, which manage the references to nodes [which may be] located elsewhere on disk. And there are two kinds of references, direct and symbolic. Direct references are simply disk offsets to where other nodes are located. Symbolic references are either by name or by pathname. Note that without symbolic references the only graph that can be represented in a COW database is a tree.

One thing to keep in mind when discussing the graph of nodes is that not every node is a member of this graph. There are also internal nodes which are used to hold the content of a node when that content becomes so large that it is not practical to read and write it all together. Case in point, some nodes are assigned the capability of a b-tree. The content of the leaf nodes of the b-tree are collectively treated as if they were the content of the b-tree's root node.

CowDb's Graph

There are three nodes which are always present in CowDb: the Root node, the Allocate node and the System Index node.

The Root Node is the only node with assigned locations on disk. This node is responsible for managing the database, so blocking updates to the database is done by updating a flag in the root node. Because of the fixed spaces assigned to the root node, it is essential that it not grow too large. So almost everything is delegated to the Allocate and System Index nodes. The RootNode, OrderedNodeMapApp and PHandle classes are used to implement the root node.

The Allocate Node is a child of the Root node and is responsible for managing all the freed and available disk space. Ahh! Note the distinction here--freed space is space that was freed during the current transaction. This space is then released and made available for reallocation at the start of the next transaction. The PNode and AllocateApp classes are used to implement the allocate node.

The System Index Node is the other child of the Root node and is responsible for managing the various versions of the content of the database. All the children of the System Index node are root branch indexes. These branches can be created empty, or as a virtual deep copy of another branch. In either case, creating a branch is a very fast operation. The IndexNode, SortedNodeMapApp, IndexHandle, InternalNode and RestrictedHandle classes are used to implement index nodes, including the System Index and root branch index nodes.

Index Nodes

From a practical perspective, there is aspect of Copy-On-Write technology which needs to be addressed: When a node is updated, it is written to a new location on disk and the parent node holding a direct reference (the disk location) must be updated in turn. It is important then to keep the depth of the graph (looking only at the graph of direct references) small and to minimize the size of the non-leaf nodes as well. CowDb's solution for this is the use of Index Nodes.

Index nodes form a shallow tree and the size of the index nodes themselves is minimized by restricting their use to holding only direct references to other nodes. Graphs are then constructed using mostly symbolic references.

Names Pathnames and Well Known names

Every node and handle have a name. A pathname is literally that--the name of the handles (links in the graph) to be transversed. And the absolute pathname is the list of handle names starting from the root which takes you to a given node. Pathnames, however, are confined to a branch and it is the root branch index (not Root and not the System Index) which has a pathname of "/". Another point to remember about CowDb pathnames is that "." refers to the local index, not the current node, and that ".." refers to the parent index of the local index.

Now because of the way indexes are used, what with indexes holding the direct reference to most of the nodes in a branch, the names used are often either UUIDs or timestamps just to assure uniqueness. And looking through the content of an index will give you a lot of uninteresting junk. So every index has an associated WellKnown Node which maps meaningful names to interesting nodes. And when you ask a node for its absolute pathname, it will use its well known name (if it has one) rather than its regular (unique) name.

Managing Symbolic References

Complex graphs can be difficult to keep up to date. Change the name of a handle or freeing a node can require a lot of application code and tends to be buggy. To solve this problem, each root branch index has a links and a backlinks table for tracking and maintaining symbolic references. Freeing a node in CowDb does not result in dangling links to a non-existent node.

Disk Space Management

As all nodes participate in a tree whose links are all direct references (or alternately a node is embeded in another node), garbage collection is not necessary. Delete a node in the graph and all the embeded nodes and directly referenced nodes are freed. The real problem is in dealing with deadwood--junk nodes accessible only via its direct reference in an index. To handle deadwood, CowDb has a simple rule: "When a symbolic reference to a node is removed and the only remaining access to that node is via a direct reference from an index node, then delete the node."

Fast Deep [Virtual] Copies

Making a fast deep copy is easy when using COW technology--just create another handle with the same direct reference. But space management gets a tad tricky. Often as not, you can only make branches at the top level. CowDb does allow branches at multiple levels, but imposes two restrictions:

The handle holding the direct reference to the node being copied must be in an Index Node. And
The handle which will hold the second direct reference must be in the same Index Node.

And what exactly gets copied? In addition to the node being copied, all the nodes which that node holds direct references to also get copied. Because that's just the way COW technology works. It also means that if you make a copy of a b-tree, all the internal nodes used by the b-tree are also copied. It is really a virtual tree copy, and b-trees are of course... trees.

OK, what about the symbolic references? Hmm. This is where we say deep copies are fast, but do not occur in fixed time, as CowDb does a bit of extra work to maintain the links and backlinks tables. If node A has a symbolic reference to node B and node A is cloned, then both node A and node A' have symbolic references to node B. But if instead we cloned node B, then node A has a symbolic reference to node B but it does not have a symbolic reference to node B'.

An Advanced Threading Model

CowDb is not a toy, but is intended for a demanding production environment. For example, you can block updates to a database so that a backup can be made without interupting queries--so it is all set for a 24X7 operation. Here's the threading model:

Only one thread can update a database.
Within a given branch, multiple threads can perform queries or one thread can perform updates. I.E. Queries and an update can be done on the same database, just not in the same branch. So if you want to perform a long-running queries, it is best to create a separate branch for it to run in. (End of day reporting then can be done without blocking updates!)

CowDb is Light Weight

Only a small amount of space is reserved for the Root Node. Everything else is variable length (which is a natural fallout of using COW technology). So if you have only a small amount of data, you may find yourself using only 1 or 2 KBytes of disk space.

A consequence of this is that small programs which require robustness can take full advantage of CowDb's crash-proof nature without incurring any significant overhead.

Application Classes

Virtually every application of CowDb will require the new App classes to add application-specific logic. Fortunately this is easy to do, but a good starting point is to look at the App classes included in CowDb.

Attribute Classes

Attribute classes extend App class and implement the IAtt interface, with its void Set(Object object) and Object Get() methods.

The attribute classes included in CowDb are far from comprehensive, though they are the easiest to program:

Role Constant	Type Constant	Class Name	Description
BOOLEAN	BOOLEAN_APP	BooleanAttributeApp	persistent boolean
INT	INT_APP	IntAttributeApp	persistent int
LONG	LONG_APP	LongAttributeApp	persistent long
STRING	STRING_APP	StringAttributeApp	persistent String
TEXT	TEXT_APP	TextAttributeApp	persistent String
BYTES	BYTES_APP	BytesAttributeApp	persistent byte[]
SERIALIZABLE	SERIALIZABLE_APP	SerializableAttributeApp	persistent container for Serializable objects

Map Classes

The Map App classes give a node the capability of holding other nodes and of holding references to other nodes. CowDb includes two Map App classes.

The SortedNodeMapApp Class is an implementation of b-tree. It has the advantage of being fully scalable and spreads its content across as many internal nodes as needed. This class is used extensively in CowDb to implement a number of different roles, including index, well known, links and backlinks.

The OrderedNodeMapApp Class is not scalable as it makes no use of internal nodes. It does provide the nice feature of allowing you to order its contents, which is handy if you want a properly ordered list of the days of the week or the months in a year. This class is used in CowDb to implement the Root role, but it is the heart and sole of COODBMS.

Role Constant	Type Constant	Class Name	Description
SORTED	SORTED_NODE_MAP_APP	SortedNodeMapApp	Fully scalable persistent container whose content is ordered by name.
ORDERED	ORDERED_NODE_MAP_APP	OrderedNodeMapApp	Persistent container whose content can be arranged (i.e. a list).

Programming Guides

#Releases?

Releases

release 3.4.3:

Bug found/fixed in the fork logic.

release 3.4.2:

Methods PElement.addPathnameReference was calling MapApp.makeSymbolic, which does not work for wellknown names due to the side effect of deleting the handle in the wellknown table when a wellknown name is removed. These methods now call addSymbolic and the makeSymbolic methods (now having no usages) have been dropped.

release 3.4.1:

Method PElement.getKey was not handling the simple case of direct links--fixed.

release 3.4:

New validation logic examines all content of a database, checking for memory leaks and duplicate usage, as well as validating pending frees associated with a fork.
Bug found/fixed: sorted elements were not freeing their content when they were freed.
Bug found/fixed: objects were marked dirty when they were read, forcing unnecessary updates.
Bug found/fixed: the fork logic was causing database corruption.
Samples now include validation checks.

release 3.3.5:

Bug found/fixed: forkBranch was saving the new branch processor in the branch processor table under the old branch name.

release 3.3.4:

Bug found/fixed: A transaction abort forces the root to be reread, but the ordered app was not clearing the name list prior to reloading.
Bug found/fixed: Wellknown name not cleared when adopting the fork of a wellknown.

release 3.3.3:

Bug found/fixed: The add operation on an ordered node was not removing the old name. Consequently an iterator would encounter the same name in more than one location.
Database names must now end in ".cowdb".

release 3.3.2:

Common has been folded into the CowDb jar file.
DefaultConfiguration class has been renamed to DatabaseConfiguration and, if passed the name of a database file, tries loading a .cfg properties file by the same name. Failing that, it attempts to load the default.cfg file.
DbProcessor instances were not added to a global map, resulting in duplicates for the same database and also lost file handles.
As a close operation needs to wait for current processing to complete (it is graceful), additional logic was needed to prevent a db from being opened while it was in process of being closed.

release 3.3.1:

Bug fix: Serialized objects held by an Entry were not being cloned--the reference was shared.
EXpress has been moved to common.
The common portion of Display has been moved to common.
Element is now PElement for consistency with PHandle.

release 3.3:

Wrote the javadoc for the org.agilewiki package.
The common package has been reorganized and cleaned up.
Node has been renamed as Element for consistency with ICommonElement and ElementModel.
Attribute Apps had a name clash with attributes and have been renamed Entry Apps, which is consistent with Rolonic terminology.

release 3.2:

CommonObject and Base64 have been moved to a "common" jar file, allowing their use without any extra bagage. (COODBMS's Document Rolon Model has no other dependencies.) This is a first small step to separate client/server processes.

release 3.1.1:

Name is now persisted as an attribute--otherwise problems with round trips.
Symbolic references are now expressed in XML as text content rather than as an attribute--again, to avoid round-trip issues.
The factory now sports the String eXpress(PNode node) method for expressing nodes as XML.
Bug fix: Xpress was displaying too many handles. Now its output is similar to Display--only handles with symbolic references are displayed.
Bind now supports well known names.

release 3.1:

The test suite was not updated in 3.0.3--the static includes were left out.
The order of the eval method's arguments was inconsistent.
A common object now handles all attribute processing.

release 3.0.3:

Reorganized the constants; replaced implements with static include. The javadocs look a lot better as a result.

release 3.0.2:

Several of the specialized handles did not support direct links, which are needed when internal nodes are created, i.e. when the root node splits.

release 3.0.1:

Small bug in the way Xpress trims text content.
Small change to PHandle to support COODBMS's rolon-relative pathnames (which begin with @).
Small bug in Ordered App Map--not expressing or binging the ascension attribute.
Problems found in PNode.resolvePathname when called from an Ent subclass.

release 3:

Persistent action classes needed to describe API calls.
As Display and XmlBind are part of eval, factory support is now required.
Sample 3, which deals with defining new persistent objects, now sports an eval method to show how to extend the COODBMS scripting language.
With Action App subclassing Ordered App, there are going to be a lot of empty ordered nodes and Ordered needs to be optimized for that.
Bytes and Serializable need to make use of text content for XML binding and expression.

release 2.2:

A text att for text content.
Xpress needs to be able to display text content.
XmlBinder needs to support text content for attribute app classes.
The wellKnown method was not using a unique name.
New tutorial on XML transformations.

release 2.1:

Reimplemented the remove method on the sorted app iterator.
Xpress, a new helper class, can be used in place of the Display class to create XML frgaments.
XmlBinder, another new helper class, parses xml and transforms it into a graph on nodes. Serializable and Bytes are not [yet] supported, and there is only minimal support for the string att. Output from Xpress is compatible with the input to XmlBinder.

release 2:

Drop the addReference and makeReference methods in favor of add and make, and instead the choice between embeding a node in another or saving it in its own disk area can be determined by an additional flag on the role specification of the node being created. In addition to making the API clearer, this will also simplify things when transforming to/from XML--which is a feature planned for COODBMS.
Had to drop remove from the b-tree iterator.
Fixed a bug in the b-tree isEmpty method.
Fixed a bug in the removal of empty inodes in the b-tree.

release 1.1.1:

Add method Iterator prefixIterator(String prefix) to PNode. This is a convenience method over rangeIterator.
BackLinks did not display properly. The bug was introduced when implementing direct pathnames.

release 1.1:

Direct pathnames for use in symbolic references.
Encode role names when persisted.
maps which do not have embeded nodes do not need to carry role names.
move fork logic from PHandle to IndexHandle
Create a minimal handle base class which only implements the common features. The various handle types must then persist the specialized data that they require.
Drop calendar--not needed until JOODBMS and it can be implemented there.
The getPObject method nees to be exposed in IMap and on PNode.
Display needs to support optional attributes, like well known name and the immutable name flag.
bug fix: Incorrect handle class being used in sorted maps when large.

release 1.0.3:

Bug in up method when an index uses internal nodes. Introduced the PNode owner() method to which internal nodes are transparent.
Added boolean isRole(String roleName) method to PObject.

release 1.0.2:

Spurious link and backlink tables were being created for every index rather than just for root branch indexes.

release 1.0.1:

A bug in the b-tree split logic has been identified and rectified.
Subclassing PHandle is now fully supported.
PHandle class is no longer parameterized. PHandle is now the base class and 5 subclasses have been implemented to support various roles.

release cowdb1.0:

The architecture of CowDb has been reworked for greater extensibility. Logical blocks have been split into nodes and apps.
A new API has been implemented to take full advantage of the new architecture and to provide a simplified view for the application programmer.
Configuration of nodes is now role-based.

release cowdb0.12.1:

A handle should also consider its name immutable when it holds a direct reference to an object with an immutable name.
Bug: When resolving a pathname to a handle, if a plist holds a container (rather than a reference to it), an exception was thrown.
On PList, iterator and sortedIterator were reversed.
Backlink removal notification has been implemented.
On CowdbFactory, the plugin method now takes an added argument--the handle type.
PList now sports nextKey and previousKey methods.

release cowdb0.12:

Fixed and refactored handle clean method for direct links.
The free method can now be called and gracefully removes an object.
The immutableName flag has been moved from PHandle to PObject. (Breaks backward compatibility.)
The display class used to create sample output has been cleaned up a bit.
Iterators have been fixed--objects are freed after the remove.
Introducted IPContainer--an interface for containers.

release cowdb0.11.4:

Bug fixed: Remove method on PList iterator not expecting non-logicalBlock entries.
Bug fixed: Disk space not being properly freed.

release cowdb0.11.3:

Defined handle types (based on container type) to decouple PHandle logic from container type.
Indexes no longer support symbolic links (examples updated).
Moved logic for removing handling well known names into PLogicalBlock where it is more easily subclassed.
Moved symbolic link removal logic into PObject/PLogicalBlock where it is more easily subclassed.

release cowdb0.11.2

Bug fix: Changing the name of a symblic link should not change the item referenced.

release cowdb0.11.1:

Additional methods added to PList for use by OODBMS: AddPObject(String type), firstKey(), lastKey() and sortedIterator()

release cowdb0.11:

Fixed a bug in lists relating to forks.
Extended lists to hold PObjects as well as PHandles--needed for COODBMS.
XTable has now been replaced by PList.
(Backward compatibility has been broken in this release.)

release cowdb0.10.3:

Lists now support the changeKey operation.

Release cowdb0.10.2:

Added lists.

Release cowdb0.10.1:

Bug fix--Reference counting should now be working.
Dropped two table types.
PBytes and PSerializable classes are now loaded on demand.
Renamed methods getHandle to getMyHandle and getContainer to getMyContainer.

Release cowdb0.10:

Bug fix--entries in links table are now removed when the symbolic link is cleared.
Key values are no longer duplicated on disk.
Handles now carry a flag for immutable names.
PObject classes are now loaded on demand.
The fork method no longer takes a name.
Plugins are supported for extensibility.
Reference counting is used to remove inaccessible PObjects.
The well known, links and backlinks tables now have well known names.
(Backward compatibility has been broken in this release.)//

Download in other formats:

Plain Text

agilewiki