Saturday, January 08, 2011

jSuneido Immutable Database

I've made a good start on rewriting the jSuneido database as an immutable persistent data structure.

It's hard to know what to call it. Overall, it's not immutable, since you can add, update, and delete like any database. The "immutable" part is that once data is written to the database file it's never updated.

You could call it "append only" because you only ever append to the database file, never update. But again, that sounds like you can't update or delete, which you can.

I started bottom up, writing a persistent hash trie to store the redirections. This is similar to my persistent hash map but designed to be stored in the database file. I also rewrote my memory mapped file access, simplifying it a lot. Now I'm working on the btree code.

The code seems a lot cleaner this time. Of course, it always does at the beginning of a rewrite because you haven't handled all the details yet. But I'm still optimistic.

As usual I'm struggling with how much to optimize. The conventional wisdom is that you write the code and then if it's too slow you profile it and optimize the problem areas. But what is "too slow" in a language or a database? You always want as much speed as you can get (without sacrificing robustness and maintainability). And that wisdom assumes that speed problems will be localized. But if the slowness is spread diffusely through the code, then it's not so easy to optimize after the fact. It's a bit like saying you can add good design after the fact.

A big part of performance is the right algorithms. Another part is implementing those algorithms efficiently on your platform. If I can "cut with the grain" of Java I think I can do more with less.

I have a lot better handle on Java and the JVM than I did when I did the first implementation. And at that point I was simply trying to port the cSuneido code, not redesign it. Now that I have a working implementation I have the freedom to explore alternatives. And I'll have something to compare performance to.

It won't be till I get to the transaction code that I'll really see how this redesign will work out. I'm hoping that the immutability of the database will simplify transaction handling. We'll see.


andreisavu said...

Link to source code?

andrew said...

Code is in Mercurial on SourceForge

Warning: it's not well tested and it is likely to change.

notzippy said...

Android port ?

(Yes I th ink I am v ery funn y)


andrew said...

Actually, that's probably not that crazy. They've managed to get jRuby running on Android, and jSuneido would be easier than jRuby because Suneido doesn't let you modify classes on the fly like Ruby does.

You could compile your Suneido libraries to a regular jar file and combine that with the jsuneido.jar

But I'm not sure how well Android handles things like memory mapped files that are used by the database code.

notzippy said...

I was being funny - not crazy :-/

For the most part it seems file management is similar to the desktop (which it should since it is an implementation of a JSE), so it should follow that the only "port" would be the implementation of the UI..


BartV said...

I see this kind of database as a "historical" DB, since evry action is logged and never touched again. So perhaps something like Suneido's HistoDB could be a naming idea?