InfinityDB

New Dynamic Bulk Loader

InfinityDB now comes with a 'dynamic bulk loader' class called ncrementalMergingItemSpace that can keep a database up-to-date with high speed while still allowing concurrent retrievals. Inserts flow in at 10 to 100 times the speed of non-local random insertions into a normal InfinityDB, and cause a minimum of seeking. The cost is that retrievals and deletes slow down - from 1 to 30 times or more. The slowdown is most noticeable with non-local access, because multiple logical ItemSpaces must be searched due to the fact that data is kept in a hierarchy of 'batches' of various sizes. For localized access, retrieval performance is much better, since once all of the blocks for each of the batches is in the cache, they may
all be sequentally or locally read without extra I/O.

For example, a stock brokerage may need to have a continuous flow of data that is immediately up-to-date, and may need to do simple queries such as access on a given customer account or transaction id. The IncrementalMergingItemSpace will reflect the Items being inserted immediately, while the queries will still run at reasonable speed, since the required 20 or so block reads will still take only a fraction of a second.

The alternative to a dynamic system like IncrementalMergingItemSpace is to load data on a schedule, such as once every day or every few hours. The data then must always be stale. Performance of the InfinityDB bulk loaders is higher than that of IncrementalMergingItemSpace, but they must build entire databases on each run.

See docs/manual/dynamic-bulk-loading.html.

New Sort Engines can be used as Bulk Loaders

InfinityDB Now comes with two high-speed Item sorters for bulk sorting of large sets of Items. The API is extremely simple, consisting of only a few basic methods and classes for use within an embedded system that also contains an InfinityDB database instance. Bulk loading data into an InfinityDB database can be accelerated dramatically by providing the Items in sorted order, so that they all go at the end of the BTree as it builds up, rather than at random positions in the database. Random access incurs slow disk seeks, but sorted input appends data directly to the end of the database file. You can see the performance improvement for yourself by running the new example programs provided with InfinityDB.

The sorters use an efficient sort/merge algorithm that requires minimal, controllable temporary space on disk. One sorter provides maximum disk space efficiency, while the other provides maximum speed. There is an 'ItemSpaceBased' sorter that keeps all temporary data in InfinityDB instances. This sorter gains from the high compression efficiency of InfinityDB itself, which is always good and can be as high as 10-fold. The 'DiskBased' sorter keeps temporary data in a very simple uncompressed form for faster, sequential transfers.

The API requires only instantiating a sorter, inserting Items into it, getting an Item reader object from the sorter, and reading back the sorted Items. (It is easy to use the sorters for virtually any kind of efficient sorting job, because an Item can contain virtually any kind of data - see the docs/manual/basic-operations.html).

For a complete description of these sorters, see the manual in docs/manual bulk-loading-and-sorting.html, as well as the Javadoc, which has extensive explanations of the sorter usage. These docs are available in the trial and deployent downloads. The classes are called ItemSpaceBasedMergeSorterItemOutput and DiskBasedMergeSorterItemOutput.

New betas: VolatileItemSpace, DeltaItemSpace, and ItemSpace set operations

Many users have asked for an 'in-memory' ItemSpace to handle fast, flexible data storage but without the need for an associated file and another background 'IndexUpdate' thread. The new VolatileItemSpace does just that. It is somewhat faster than InfinityDB in general, and much faster for small db's - in the tens or hundreds of Items. VolatileItemSpace uses the technology in the 'meta access method' inside InfinityDB for speed while exposing exactly the same client view as all other ItemSpaces, making it useful as a drop-in component in a wide variety of situations with no client code change at all.

Another new ItemSpace is DeltaItemSpace, which allows a virtual modification of a base ItemSpace, which is not modified, followed by an optional rollback of the changes or an application of the changes to the base ItemSpace. The applications for this ItemSpace are endless: for example, a transaction can use it for simple atomicity (see the new manual for more), or a GUI can provide a CANCEL button that rolls back the deltas and leaves the db unchanged.

ItemSpace now supports set operations like union() and intersection(), as well as deleteSubspace() and others. There are currently only default implementations of these, but smarter ItemSpaces can override them and increase speed for some operations. For example, InfinityDB may be able eventually to delete quickly all Items with a given prefix by overriding deleteSubspace(). The intersection() implementation is very smart, using the 'zigzag' algorithm described in docs/manual/andorspaces.html.

There is also a new manual in docs/manual/index.html. Even if you are an experienced InfinityDB user, we would appreciate feedback on it.

Prefix compression - It affects your world view

David X wrote:

> Dear Support,
>  
> Suppose I enter a number of people in the database as below:
>  
> // persons[]:  array of person names to add to the 
< database (n == numberOfPersonsInArray)
> for (i=0; i<n; i++) {
>     cu = cu.clear().append(ENTITY_TYPE).append("person").append(person[i]);
>     db.insert();
> }
>  
> Keeping in mind that .append(ENTITY_TYPE).append("person") are always 
> constant, I would expect the tree to look like the following:
>  
> //                     "ENTITY_TYPE"
> //                           |
> //                         "person"
> //                           |
> //              +------------+--------------+
> //              |            |              |
> //           person[0]    person[1]  ... person[n-1]
>  
> However, "ENTITY_TYPE" and "person" are also stored in the database 
> "n" times, not once like I expected.
>  
> I would like to know how to think about "ENTITY_TYPE" and 
"person", which I look at as singular entries, but are not.  
I assume this has to do with each append() putting a new pointer into the database.
>  
> I am not having any problems with this, because it all works fine; 
but I am wanting to build a hierarchy from this information, and 
the multiple entries for each "ENTITY_TYPE" and "person" surprised 
me (the hierarchy can still be built by ignoring duplicate entries).
>  
>  
> David
>  

Yes, thought about as a completely independent series of Items, it does look
like there is duplication of the EntityClass and Entity when  you  use next() to
scan over a subtree or 'subspace'.

I think you have to remember the way the next() and other operations work
with a protected prefix length. That protected prefix length will always cover the part of
the Items that are to be considered 'higher' in the tree the way you drew it,
so that higher part of the data does not change in the Cu. When you use next(), you are
always only looking at the changes in the Cu beyond that prefix length, and you
ignore the common prefix. So the fact that the prefix is still sitting in there unchanged
really doesn't matter practically.

>From the perspective of any ItemSpace, Items are actually only simple variable-length
char sequences kept in order, but they are basically
always stored in the database with prefixes shared between adjacent Items
compressed out at the character level. This compression is transparent, though, so
there is no way any user of an ItemSpace can know that prefix
compression is going on. However, it would just be so ineffiicient to store
the common prefixes that you get used to assuming that that
prefix compression is going on, and the apparent duplication of the prefixes
when you just list out the Items in sequence doesn't bother you after a while.
The ItemEditor shows the apparent duplications as well, and you just have to look
past that.

So there actually aren't any special internal pointers or other tricky stuff
going on. An ItemSpace is just an ordered sequence of Items, each Item  is
a variable-length sequence of up to 1600 chars [which is not a significant
limit due to the ability always to structure data in ways that avoids 
the problem - ed]. The higher-level meaning
of Items as a series of components is actually not something any ItemSpace knows
about. That's why it's so easy to invent new ItemSpaces, like the DeltaItemSpace
or the VolatileItemSpace in the latest release. The concept of components is
actually totally restricted to the append(), skipXX(), and other operations on Cu.
(In fact you aren't even restricted to use those component-oriented
operations: you could invent your own meaning of the chars in the
Item by using raw operations like Cu.appendChar(c) and so on.)

One way you would be concerned about the apparent duplication of initial prefixes would be
if you wrote a simple database dumper that scanned all the Items in the db using
db.next(cu,0) and then wrote each Item out as a raw sequence of chars. There
would be no compression of shared adjacent prefixes, and the output would be
rather inefficient. It would be easy to fix that dumper to output only the
suffixes that actually change from Item to Item. That would be as efficient as
the InfinityDB internal compression.

I agree with you now that I think about it that that apparent duplication of
prefixes is a bit disconcerting at first. But the whole Idea of an EAV-structured
database, or even most of the other ItemSpace-based structures you might use, depend on
the internal compression inside the ItemSpace implementation for efficiency.

Good point.

Roger

Nio File Channel Locking is Now the Default

On the latest version of InfinityDB, as of 5/18/06, the
Java nio channel locking feature has become the default.
From now on, if InfinityDB is running on a JVM 1.4 or
later, files will be locked using the native locks as
described in the previous blog.

New File Locking

The latest version of InfinityDB includes an option for InfinitydDB.open() and InfinityDB.create() that provides Java 1.4 nio native file locking. These options are recommended for all future development in order to prevent sharing of InfinityDB files by multiple processes.

The nio native file locks solve a long-standing problem for any application that needs to prevent inter-process concurrent access to file data. Simple solutions that have been tried in the past, such as using a separate lock file, have virtually all failed in some circumstances, although it has been reported that a certain technique using File.rename() actually does work. If you are using a custom scheme, please try to switch to the new system.

There is no change to the existing behavior of any InfinityDB API. If you are using InfinityDB in a J2ME environment, or anywhere else that does not allow Java 1.4, such as in memory-constrained devices, the nio locking is automatically bypassed.

Overlapping Commit in IDB 1.0.40

The new online trial download of InfinityDB is v1.0.40, and it contains a new performance enhancement. If you activate it using InfinityDB.setOverlappingCommits(true), you will see a large performance improvement in situations where multiple Threads continuously do multiple inserts or deletes followed quickly by commits. In this case, commit passes can overlap, thereby executing the commits for most or all of the threads at the same time. Previous versions of InfinityDB always serialized commits.

Compare Java Edition with InfinityDB

The trial download now includes testers that enable direct comparisons between two embeddable database engines: Sleepy Cat Java Edition and InfinityDB. Using compressible data, the tests show that InfinityDB is 13 to 22 times faster and from 37 to 100 times more space efficient because of its unique dynamic data compression. Our clients typically subject the Infinity Database Engine B*Tree to performance, stress, and scalability tests and prove for themselves that it outperforms the Java edition. They choose InfinityDB for performance, incorruptibility, compression, and simplicity, whether it is to be embedded in server applications; throughout a distributed system for storage of configuration data; or within a PDA application.

We appreciate our customers who do this work for themselves, but now we offer our own testers, to speed the initial evaluation. These tests support our claims, while revealing how to code with our API. Access the download link from our home page.

InfinityDB is cost effective whether you are comparing it with the Java Edition or to rolling your own in-house data store. Its simple API and single file architecture simplifies the design and implementation phase; its incorruptibility eliminates support issues; its high performance enables the most powerful server applications; its extreme compressibility saves hardware; and its small footprint makes it embeddable in PDA's.

We are happy to recommend the best strategy for employing our flexible data model for your particular circumstances -- we even provide up to three free hours of support.

Check out our white papers and the other blog entries.

We look forward to hearing from you.
Jennifer Douglas
Licensing and Support Director

Performance with Compressible Data Better than Expected

We recently added a performance tester to the examples directory of the trial and deployment downloads: InfinityDBPerformanceTest.java. The results were pleasantly surprising. When tested against a common form of compressible data, speed and disk space efficiency for all operations improved dramatically. We have been quoting 30K inserts/sec/GHz, but with this rather typical compressible data,we are getting 120K insertions/sec/GHz, in a warm cache (with no disk I/O, i.e. all data in the cache). The cold cache performance (which requires allocating cache blocks during warmup) is only slightly slower.

The performance for pure random data is roughly what we expected, with next() being a bit slower than expected, and insert()/delete() somewhat faster.

Data compression was also dramatic: 20MB of compressible data was stored in 1.4MB. Data compression for purely random data is only 28% worse than the theoretical minimum, with the 20MB stored in 25637K bytes. A recent third-party potential client found that the database generated by the SleepyCat (Berkely DB) B-Tree took 140MB for similar purely random data.

This compressible data uses repeating 10-byte prefixes and repeating 10-byte suffixes. The former is common in many uses of the engine (see ItemSpaceDataStructures.htm). The Latter simulates attribute values with small numbers of distinct values. Also, the ZLib compressor got going with its Huffman coding because we used only 40 values per byte, simulating common English text.

Please examine the tester itself and try changing various parameters. Access the download link from our home page. Here is the actual output:

Performance test of InfinityDB B-Tree database engine.
File=c:\temp\InfinityDBPerformanceTest.idb
Entries=1000000 bytes/entry=20

RANDOM COMPRESSIBLE DATA

insert with cold cache, compressible data time=3.6259999999999994 iterations/sec=275785.9900717044
compressible db size=1420075
next with compressible data time=3.5159999999999996 iterations/sec=284414.1069397042
delete with compressible data time=3.6409999999999996 iterations/sec=274649.8214776161
insert warm cache, compressible data time=3.3129999999999997 iterations/sec=301841.2315122246

RANDOM UNCOMPRESSIBLE DATA

insert cold cache, uncompressible data time=14.219 iterations/sec=70328.43378577959
uncompressible db size=25637958
next with uncompressible data time=7.561999999999999 iterations/sec=132240.1481089659
delete with uncompressible data time=9.577 iterations/sec=104416.83199331732
insert warm cache, uncompressible data time=9.39 iterations/sec=106496.27263045793

Performance test done.

Db copying, merging, defragmenting, and linearizing

Sometimes it is percieved as desireable to linearize or 'defragment' an InfinityDB B-Tree database to increase speed or restore the almost perfect space utilization of a newly created db. (Note all db's use the UTF-8 and ZLib data compression at all times.) While this is not necessary in general, and has not been done in the past by most clients, it can be done with a trivial amount of code, as shown below. All internal free space - blocks on the free list - will be reclaimed, and the variable-length block storage format will allow extremely dense packing of data inside blocks. Linearizing the blocks should increase speed for sequential operations as well.

Note that there is almost no 'internal' free space, i.e. per-block overhead, because blocks are stored variable length; the average waste can be as low as a few percent. So, when we refer to free space, we always mean the 'external' free space; we mean the free space external to the block, which constitutes a set of empty blocks on a 'free list' inside the single db file. Free space is always used during any modification before the file is extended.

Significant amounts of free space necessarily occur when a large number of blocks are deleted or when there are a very large number of random updates before a commit. Sequential updates - those affecting Items close together - will only dirty one or a few blocks, so each batch can be considered equivalent to one random update operation. If commits are done reasonably often, free space can be kept well below ten percent, with 5% not uncommon. Committing after every few random updates will keep free space almost non-existent, at the expense of performance, of course, since a commit writes several blocks and forces them out with a FileDescriptor.sync(). The FileDescriptor.sync() is the slowest part, and is the only way any DBMS can be sure data has been written to disk, so that a transaction becomes durable. The commit overhead can be spread out over a resonable number of modifications. The worst-case utilization due to random updates is 50% if every page in the database is dirtied before a commit(). The utilization in this case will go back up to nearly 100% as usual as data is inserted in the future. Note that this free space should be looked at as a proportion of the original uncompressed data, so it may be effectively much smaller.

These characteristics can be understood by considering that all blocks currently containing data in the db are left intact until the moment of commit, when the obsoleted blocks move atomically to the free list. Dirty blocks migrating out of the cache are kept in the free space until they become valid data atomically at commit().

Here is the simple code for copying an entire db:

   void copyDb(String source, String dest) {
       InfinityDB sourceDb = InfinityDB.open(source, false); // false=readonly
       InfinityDB destDb = InfinityDB.create(dest, true); // true=overWrite
       Cu cu = Cu.alloc(); // get a cursor from the free list of cursors
       try {
           while (sourceDb.next(cu)) { // get the next Item from sourceDb into the cursor
               destDb.insert(cu); // put the Item into destDb
           }
       } catch (IOException e) {
            e.printStackTrace();
       }
       cu.dispose(); // optional, for speed
       sourceDb.close(); // release FD to be nice, free the cache
       destDb.close(); // this also commits
   } 

This code will also merge sourceDb into destDb if destDb is not empty (use open(), not create()).

Because the InfinityDB B-Tree is fully Thread-safe and concurrent, it would also be easy to experiment with a multi-Thread version for use on SMP or RAID systems. The file might be partitioned by starting Each Thread's Cu at a different place, for example. Tell us if you do this - we'll report the results here.