db4o has yet another Freespace Management System. This one is built on top of BTrees.
Let's take a look at what freespace is all about:
When an object is updated, it is written to a new or free slot in the database file. This way commit can be an atomic operation that changes the pointers of all updated objects to point to the new slots.
After commit the old unused slots can be made available for future use. They are passed to the FreespaceManager where they are merged with adjacent free slots. The FreespaceManager is in charge of delivering the "best" match to a request for a slot of a certain length, ideally one that already has exactly the length that is needed. If such a slot is not available, a chunk of the next bigger sized slot is returned and the remainder is kept on stock for future requests.
All of our FreespaceManagers implement the above behaviour by holding the free slots in two trees, one sorted by length, the other sorted by address.
So far we have already had two FreespaceManager implementations:
(1)
Db4o.configure().freespace().useRamSystem();
This implementation is used by default. It reads all freespace into trees in RAM when a database file is opened, holds it there all the time while the database file is open and writes it back to the database file when the database file is closed.
(2)
Db4o.configure().freespace().useIndexSystem();
This FreespaceManager uses our old index implementation back from the times when we did not have a BTree implementation yet.
The above two systems have shortcomings:
RAMFreespaceManager
- If a system is halted without being shut down correctly, all freespace is lost. This can be a common scenario on handhelds that frequently get turned off while they are running.
- Freespace nodes that are held in RAM consume extra space. The amount of used memory can be quite relevant on low-ressource systems.
IndexFreespaceManager
- The old index is fully file-based and does not do any in-memory caching.
- It is very slow.
- It uses quite a lot of memory on commit to reorganize itself.
Our latest third implementation uses our BTree implementation, which is proven to be very fast:
(3)
Db4o.configure().freespace().useBTreeSystem();
We have written a circuit for the Poleposition benchmark specifically to test the behaviour of the three freespace systems against eachother.
Here are the results. The default implementation is red, the new BTreeFreespaceManager is green and the old IndexFreespaceManager is blue:
http://www.db4o.com/downloads/BTreeFreespace.pdf
Naturally there is a performance penalty for deletes and updates in comparison to the RAM-based system.
The memory graphic looks like we have done a good job. The new BTreeFreespaceManager (green) clearly has a much lower memory consumption with hardly any peaks at all:
The new BTreeFreespaceManager is in our SVN and will be released as version 6.3.
Enjoy!