InfinityDB

Db copying, merging, defragmenting, and linearizing

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
   } 

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.

RDBMS Tables vs Entity-Attribute-Value Modeling

create table metrics {
       when           timestamp,
       factoryId     varchar(8),
       machineId  varchar(8),
       metric          integer
}

    static final EntityClass METRICS = new EntityClass(0); // the 'table'

    static final Attribute METRIC = new Attribute(0); // the 'column'

    static void insertMetricReport(String factoryId,
	            String machineId, Date date, long metric) throws IOException {
	    Cu cu = Cu.alloc(); // get a work cursor temporarily

	    // create a new METRIC report entry if necessary, identified by 
	    // factoryId, machine id, and date and attach the metric to it.
	    cu.append(METRICS) // the EntityClass component
	    .append(factoryId) // next three components are the composite key
	    .append(machineId)
	    .append(date)
	    .append(METRIC) // the Attibute component is like a column name
	    .append(metric); // the Value component
	    db.insert(cu); // put all of them into db in one atomic action
	
	    Cu.dispose(cu); // Give back cursor for speed. no strictly necessary
	}

    void selectReports(String factoryId, String machineId,  
            Date startDate) throws IOException {
	    Cu cu = Cu.alloc()
	    	.append(METRICS)
	    	.append(factoryId)
	    	.append(machineId);
	    int protectedPrefixLength = cu.length(); // The current contents of the Cu is protected
	    cu.append(startDate); // start the scan here. This part is not protected, so it changes
	    while (db.next(cu, protectedPrefixLength)) { // iterate over report dates
	        printMetric(factoryId, machineId, cu.dateAt(protectedPrefixLength));
                // This cookie-cutter code allows iteration over a part of an Entity.
                // More often, this is unnecessary because we iterate over multi-value Attributes.
                cu.setLength(cu.skipComponent(protectedPrefixLength));
                cu.incrementSuffix(protectedPrefixLength);
	    }
	    cu.dispose();
    }

    void printMetric(String factoryId, String machineID, Date reportDate) throws IOException {
        Cu cu = Cu.alloc()
        	.append(METRICS)
        	.append(factoryId)
        	.append(machineID)
        	.append(reportDate)
        	.append(METRIC);
        int protectedPrefix = cu.length();
        if (db.next(cu, protectedPrefix)) { // got a report
            System.out.print("date=" + reportDate + " metric=" + cu.longAt(protectedPrefix));
        }
        cu.dispose();
    }