[elephant-devel] Lisp-only data store (prototype)

[Elliott Slaughter]

Hi,
Thanks for working on this. I am particularly interested in the potential of
this backend because I need (a) speed and (b) the ability to build a binary
which will run on end-user machines without requiring them to install a
separate library.

If you send me the necessary patches (or get them integrated into their
respective libraries), I would be happy to help you test this code on my
application.

I look forward to hearing from you.

On Mon, Feb 2, 2009 at 12:29 PM, Ian Eslick <eslick at media.mit.edu> wrote:

> Hi All,
>
> I was inspired the other day to come up with a minimal, quick-and-
> dirty, all-lisp data store for Elephant based on cl-prevalence.  The
> problem with cl-prevalence is that every access to a persistent slot
> has to be explicitly transactionally protected so it can be
> recovered.  This is onerous and violates the abstractions provided by
> the rest of the elephant data stores.
>
> The general idea is to hide the cl-prevalence transaction model inside
> the existing meta-object protocol.  Instead of the usual hash table,
> we use trees from cl-collections as our replacement for btrees and
> indexes - this gives us reasonably efficient successor/predecessor ops
> and makes it easier to implement the mapping and cursor APIs.
>
> It's not going to be nearly as fast as a full prevalence solution, but
> it will be faster than BDB and should be much easier to install and
> work with on a single-image basis.  The new db-clp store requires a
> patches to cl-prevalence and cl-containers.  I'll see about getting
> those put into the mainstream, but can send them to anyone interesting
> in hacking on this in the meantime.
>
> I checked a prototype of this into elephant-1.0 today; it does not
> interfere with existing functionality at all and I'm not sure yet
> whether it will be part of 1.0.  You can open a new store, subject to
> the following caveats, by:
>
> In elephant root: ln -s src/contrib/eslick/db-clp/ele-clp.asd ele-
> clp.asd
>
> (open-store '(:CLP "/home/me/db/"))
>
> where /home/me/db/ is a fresh directory.
>
> 85%+ of the tests pass and a ton of stuff does work: persistent
> classes, btrees, dup-btrees, indexed-btrees, mapping (mostly), and
> class indexing (mostly).
>
>
> However, there are still some very serious holes.
> The ones I'm aware of are:
>
> - You can only create, but not re-open a store
>   (this is due to a bootstrapping problem in recreating persistent
> instances
>    when loading a snapshot)
>
> - No cursors are supported (all those tests fail), but should be easy
> as there is a good match between the RB tree and the btree
> abstractions but you will need to add a couple of functions to cl-
> containers.
>
> - On-line recovery has not been tested.
>
> - I'm unsure of how cl-prevalence guarantees global transaction
> serializability - I don't see locks anywhere in the code.
>
> - I faked out a bunch of serializer tests by including the default
> serializer,
>   because they depend on buffer streams which the xml serializer
> doesn't support;
>   the tests should be fixed to be more general and not rely on buffer
> streams.
>
> - Some issues in schema evolution tests
>
> Performance issues:
>
> - Reads need to be serialized so are currently considered transactions
> for simplicity, but they write a transaction log - they should be
> rewritten to only use the serialization mechanism but not write a log
> and the grabbing of a lock during serialization should be done once
> per with-transaction call.
>
> - with-transaction is a no-op, a significant performance enhancement
> would be to bundle a set of primitive operations such as tx-write-
> slot, tx-remove-kv and write a single prevalence log entry for them.
> This would avoid a disk write per primop.
>
> - I started using splay trees, retreated to RB trees due to bugs and
> finally retreated to binary-search-trees due to more bugs.  Moving to
> a more efficient, balanced tree data structure will improve the
> performance of all operations.  However, several tests use linear
> insertion, reducing the asymptotic behavior of the tree to that of a
> list - it really grinds the tests to a halt.
>
> Obvious next steps, in order of increasing difficulty:
> - Implement cursor API
> - Fix red-black or splay tree implementation in cl-containers
> - Figure out how to load from a snapshot
> - Use with-transaction to improve performance
> - Read transaction optimizations
>
> Regards,
> Ian
>
>
>
> _______________________________________________
> elephant-devel site list
> elephant-devel at common-lisp.net
> http://common-lisp.net/mailman/listinfo/elephant-devel
>



-- 
Elliott Slaughter

"Any road followed precisely to its end leads precisely nowhere." - Frank
Herbert
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mailman.common-lisp.net/pipermail/elephant-devel/attachments/20090202/8e31859f/attachment.html>