[elephant-devel] Lisp Backend Architecture

[Red Daly]

I believe the code I attached was scrubbed. Here is a link instead:
http://iodb.org/static/persistent-heap/

Red

On Tue, Oct 28, 2008 at 10:30 AM, Red Daly <reddaly at gmail.com> wrote:

> I am hoping to clarify some of the prior discussions[1] about the native
> Lisp backend for Elephant and propose a basic architecture.  Hopefully we
> can modularize development so if somebody wants to hack for a few days on
> the backend he can avoid being overwhelmed.
>
> Multiprocess support: What features do the major lisps have for locking and
> concurrency?  What features are we missing from C/linux--what does BDB do in
> this regard that is hard to do in Lisp?  I do not know too much about
> implementing efficient multi-threaded lisp programs where there is a lot of
> contention.
>
> Distribution: Are others interested in making the backend distributed?  I
> prefer the design to allow adding an efficient distributed architecture at a
> later date.
>
> Custom indexing: A lot of discussion has gone into the best implementation
> practice for BTrees.  But what about other indexing structures?
> Multidimensional indexing is relevant to my project now because we have
> spacial information (longitude latitude pairs) we would like to query.
> Right now I am using a kd-tree with nodes made persistent by elephant, but
> usually this sort of index would be implemented by the database itself.  I
> imagine multi-dimensional indexing could improve queries, too.
>
> There are other indexing needs as well.  Document-level search is another
> common case.  I imagine an efficient search library is beyond our capacity,
> but how could we make the database suited to implement search on top of the
> thing?  BTrees are not everything, unless I am missing something.
>
>
> I propose the following basic architecture for the backend:
>
> Logging package with generic undo/redo logging support.  It would be
> customizable but it would not depend on other code from the Lisp backend.  A
> database could plug into the log by implementing undo, redo, and
> serialization functions.  By modularizing logging, it should make it easier
> to hack on it without being familiar with the rest of the backend.  It will
> also be reusable, for what it's worth.
>
> A persistent heap.  Beneath indices and data storage would be a
> heap-on-disk layer with transaction support.  The heap would have methods
> for reading, writing, and locking sequences of bytes.  It would also handle
>   The persistent heap alone would qualify as a database and might be useful
> as a basis for other DB projects or experiments.  Cachine would probably not
> be implemented at this level, though that would be easiest.  It may be
> possible to implement the transactional heavy lifting for the persistent
> heap and make it extensible enough to be used throughout.
>
> B-Trees.  A MOP-based implementation of B-Trees may be customizable enough
> to plug into the the rest of the system with a few additional method
> declarations for the persistent, transactional version.  Specialized methods
> would access the persistent heap for reads and writes.  Locking of the sort
> done by BDB (level 2 etc.) could probably be accomplished in these methods
> specialized for our persistent B-Tree.
>
> Bkd-Trees and other indexing structures could be implemented similarly to
> B-Trees.
>
> Caching.  B-Tree nodes or other lispy objects should be cached as opposed
> to byte arrays.  Caching of B-Tree nodes requires additional multiprocess
> code, so not all the transactional magic happens in the persistent heap
> layer.  I'm a little fuzzy on exactly how this will work, but it sounds
> reasonable enough.
>
> The DB user would interact mostly with the B-Tree  and other indexing
> structures, and with transactions.
>
>
> How does this sound for a basic architecture?  The multiprocess details are
> not fleshed out so your comments are appreciated.  I have attached my basic
> implementation of a logger and persistent heap to make this clearer.
>
>
> Best regards,
>
> Red
>
>
> [1]  The most lengthy discussion I can find is here:
> http://common-lisp.net/pipermail/elephant-devel/2008-May/004108.html
> The trac has a page on the Lisp backend:
> http://trac.common-lisp.net/elephant/wiki/LispDataStore
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mailman.common-lisp.net/pipermail/elephant-devel/attachments/20081028/75c72940/attachment.html>