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

Ian Eslick eslick at media.mit.edu
Tue Feb 3 16:12:35 UTC 2009

The BKNR store is very interesting!  It is a solution on-par with  
Elephant, but makes different commitments and tradeoffs.  To utilize  
their infrastructure and make it compatible with Elephant's MOP  
implementation, I'd probably have to fork the tree and split out the  
appropriate functionality.

I think that the Elephant MOP and transaction model is easier to work  
with and subject to fewer 'gotchas'.  Elephant provides ACID  
guarantees to all primitive operations both inside and outside of  
transaction wrappers.  Transactions ensure the atomicity of a set of  
operations (e.g. the account transfer example) and provide increased  
performance by reducing disk sync operations and lock grabbing/ 

I actually have a sketch of a pure prevalence solution in my contrib  
directory which is very similar to the BKNR approach, but using the  
Elephant MOP so it's compatible with other data stores.  One thing I  
hadn't thought of before is leveraging their serializer and log file  
code base rather than re-writing my own which I had started some time  
ago.  The design issue I was stuck on at the time, some of which is  
documented in the elephant-devel archives, is taking a BDB-like fine- 
grained locking approach to enable high degrees of concurrency or a  
copy-on-write / versioning approach similar to Rucksack.  I won't have  
time for quite awhile, unfortunately, to get back to a full prevalence  
or on-disk btree, lisp-only solution.  I'm happy to support someone  
who wants to take on the bulk of this work, however.

The cl-prevalence solution actually provides this same set of  
properties, albeit with a noticeable performance hit.  There are many  
opportunities to improve the performance of the CLP data store  
prototype, and of course it is not yet feature complete.  It is fairly  
small, so I don't think it would be too much work for others to  
contribute to and could be made feature complete with some concerted  
effort in a week or two.

FYI - Elephant's commitment to export a btree interface is a  
complicating factor for data store implementation.  My thought is that  
we should probably hide this over time and export a higher level  
abstraction that eschews cursors and other low level details in favor  
of a table abstraction that includes pre-order and post-order  
traversal options via mapping abstractions and/or generators.  This  
wouldn't be hard to do for 1.0, and we could maintain the btree  
abstraction as an add-on for those who depend on it.

How many people currently directly use the Btree/cursor interface?


On Feb 3, 2009, at 9:15 AM, patrice.lespagnol at obs-nancay.fr wrote:

> For information, in case you've not already look at it, beside
> cl-prevalence, there is also the bknr datastore code base that seems
> interesting.
> http://bknr.net/html/documentation.html
> Hope that can help and thanks for sharing your work on Elephant !
> _______________________________________________
> elephant-devel site list
> elephant-devel at common-lisp.net
> http://common-lisp.net/mailman/listinfo/elephant-devel

More information about the elephant-devel mailing list