[elephant-devel] Querying Advice
Ian Eslick
eslick at csail.mit.edu
Wed Nov 15 11:58:50 UTC 2006
Daniel,
There are a couple of things about the Elephant model that should be
made clear. Elephant is not a very high level DB system. It's focus is
persistence of data. In effect, it is a collection of indexing
mechanisms and a metaobject protocol that helps us to store/retrieve
data. There are three ways to persist data.
1) Put it in the root, or another BTree that you have manually created
and put in the rot
2) Create a persistent object. A persistent object has two manifestations:
a) A stub containing an OID and a reference to the controller the
object is stored in
b) A set of slot values stored in a master slot-value BTree
When you do a slot access, the OID and slot name are used to go into
this (hidden) master slot-value BTree to find the actual slot value.
This is done as a tradeoff so if you are writing an integer slot in an
object with a large string, you don't have to load that string into
memory to get ACID properties on that integer slot.
When you load a persistent object from the root or another index, all
that is loaded into memory is the stub. All slot accesses go
independently back to the on-disk store to get their values. This means
that the on-disk value and locking together guarantee that any number of
processes or threads within a process can use the same Elephant store
and guarantee ACID semantics (BDB & SQL handle locking for us). For
most lisp applications with a single image, bookkeeping like Robert's
system make more sense, but you have to worry about locking yourself.
DCM pre-loads all the slot values but updates the on-disk version on
writes for CID properties - atomicity has to be explicitly managed.
We're hoping to make slot caching a natural feature of elephant eventually.
3) Use slot and class indices. Underneath, this is just #1 with
functions to make the BTrees simple to use. When you created an indexed
object, the object is added to a BTree and a secondary index is created
for slot values on top of the master slot-value index. It's the class
index that guarantees you can reach the object.
Now if you are hacking on elephant, this is the mental model you need.
Eventually we're hoping that it becomes sophisticated enough you rarely
need this level of detail (query language, flexible persistence
semantics, etc). However the persistence of lisp values and the
persistent vs. normal class objects means it will never be perfect.
Manual deletions are actually quite hard to do in such a system, because
if you delete an object and forget to delete the references then you end
up with a corrupted data representation that will fail silently (return
garbage or null slot values) if you reload a reference. Also deleting
an object means removing it from all referring data structures and also
deleting (separately) each slot value. Thus the only safe method of
deletion is GC which is not yet implemented except by manually migrating
your DB which copies everything reachable from root & class-root. I'm a
little worried for large DBs that GC can't happen when the DB itself is
some factor larger than the available working memory. I know how to fix
that, but it's a little involved.
Some more comments below.
PS - All BDB log files start out at 10MB. They store bookkeeping
information so take up more room than you might expect from the stored
data itself.
Daniel Salama wrote:
> Ian et al,
>
> Based on my comment to Robert and that of Pierre, could you, or
> anyone, please clarify this for me (and maybe others):
>
> If making a class persistent means that there is no need to add it to
> root or to any persistent collection, when I look at Robert's sample
> code, I see (excerpts):
>
> (defclass User ()
> ((username :type 'string :initform "" :initarg :uname :accessor
> username-of)
> (password :type 'string :initform "" :initarg :pword :accessor
> password-of)
> (email :type 'string :initform "" :initarg :email :accessor email-of)
> (fullname :type 'string :initform "" :initarg :fullname :accessor
> fullname-of)
> (balance :type 'integer :initform 0 :initarg :balance :accessor
> balance-of)))
>
> (defun random-users (n)
> (dotimes (x n)
> (let ((u (make-instance
> 'User
> :uname (format nil "user~A" x)
> :pword (random-password)
> :email (format nil "user~A at .nowheresville.org" x)
> :fullname (format nil "~A~A ~A~A" (random-password) x
> (random-password) x)
> :balance (random 100))))
> (add-to-root x u))))
>
> There is an explicit add-to-root in random-users. I suppose the reason
> for this is because User class does not inherit from
> persistent-metaclass and in order to be able to "search for" or
> retrieve that object (could this also be the reason for the additional
> storage overhead, as you pointed out yesterday?). Right? So, if my
> understanding is correct, defining User with defpclass instead would
> mean that you don't have to add-to-root because it will be
> automatically persisted. However, after the function exits, there will
> be no reference to that persistent object and will therefore be
> eventually garbage collected (whether or not the persistent space will
> be reclaimed is a different story, as you mentioned in your email). Is
> that right? If so, how could I avoid for the User objects to be
> garbage collected in this case, since there really is no other
> reference to these objects after creating them? Or, if the objects are
> NOT garbage collected, how could I manually "delete" any of them?
>
> Now, if I (or Robert) had defined the User class as:
>
> (defpclass User ()
> ((username :type 'string :initform "" :initarg :uname :accessor
> username-of :index t)
> (password :type 'string :initform "" :initarg :pword :accessor
> password-of)
> (email :type 'string :initform "" :initarg :email :accessor email-of)
> (fullname :type 'string :initform "" :initarg :fullname :accessor
> fullname-of)
> (balance :type 'integer :initform 0 :initarg :balance :accessor
> balance-of)))
>
> where (notice how it's defined with defpclass) the username slot is
> indexed, the system would automatically store a reference to the
> object in the slot index, and there would be no need to use the
> add-to-root in random-users. Correct? If that's the case, how would I
> then go about removing this user object from persistence? Would it be
> by setting the indexed slot value to NIL?
See above.
> On another note, if I want to create a collection of users, I don't
> have to store these users in a collection. Simply making them inherit
> from persistent-metaclass and indexing them would do so automatically
> (just like the example above). Right? How about this, then:
>
> (asdf:operate 'asdf:load-op :elephant-tests)
>
> (in-package :elephant-tests)
>
> (setf *default-spec* *testbdb-spec*)
>
> (open-store *default-spec*)
>
> (defpclass state ()
> ((abbr :type 'string :initform "" :initarg :abbr :accessor abbr-of
> :index t)
> (name :type 'string :initform "" :initarg :name :accessor name-of)))
>
> (defpclass zip-code ()
> ((zip :type 'string :initform "" :initarg :zip :accessor zip-of
> :index t)
> (city :type 'string :initform "" :initarg :city :accessor city-of)
> (county :type 'string :initform "" :initarg :county :accessor
> county-of)
> (state :initform nil :initarg :state :accessor state-of)))
>
> (defmethod print-object ((obj state) stream)
> (format stream "State (abbr, name) = (~A, ~A)" (abbr-of obj)
> (name-of obj)))
>
> (defmethod print-object ((obj zip-code) stream)
> (format stream "Zip (zip, city, county, state) = (~A, ~A, ~A, ~A)"
> (zip-of obj) (city-of obj) (county-of obj) (state-of obj)))
>
> (let* ((s1 (make-instance 'state :abbr "FL" :name "Florida"))
> (s2 (make-instance 'state :abbr "NY" :name "New York"))
> (z1 (make-instance 'zip-code :zip "33015" :city "Miami" :county
> "Dade" :state s1))
> (z2 (make-instance 'zip-code :zip "13605" :city "Adams" :county
> "Jefferson" :state s2))
> (z2 (make-instance 'zip-code :zip "33160" :city "Sunny Isles
> Beach" :county "Dade" :state s1)))
> (print s1)
> (print s2)
> (print z1)
> (print z2)
> (print z3))
>
> Here, I'm creating a couple of state objects and a couple of zip-code
> objects. Since a zip-code can only belong to one state, they have a
> reference back to the state in order to "quickly" determine the state
> they belong to.
>
> A couple of questions/comments here:
>
> 1) If I wanted to ask a state to give me all the zip-code(s) within
> it, would I create a slot in the state class to hold a collection of
> zip-code references? Or would I simply create a state-class method like:
>
> (defmethod get-zip-codes ((obj state))
> (get-instances-by-value 'zip-code 'state obj))
>
> This does not work because the state slot in zip-code is not indexed.
> Also, from the code above, I don't know how to get a reference to the
> btree in order to create a cursor so that I can linearly traverse the
> zip-code(s) to return only those zip-code(s) which belong to that state.
Yes, you have to decide what queries you want to do and make trade-offs
between space and time. Of course it's easy to make the decision "lots
of zip codes, small ranges in queries, large number of zip codes per
state = index OR moderate # zip codes, large ranges per state, small
number of states = add a slot and use a list or array" Then you add the
:index marker to the zip code or add a new slot to state to keep track
of the association. There is no general notion of association as you'll
see below. However that might be a nice thing to add - you start to get
relational notion into the simple object persistence model.
I guess that's the confusion. Elephant is NOT an object database - it
is a persistent object and collection facility. The DB functionality
you (today) have to write yourself. It might be nice to add a layer or
two that makes it more ODB like. But as Robert has done with DCM - you
can craft an object/storage model that works for your application.
Keeping references to objects in slots is an implicit DB but it does
require that you think in a way that RDB's do not.
> Of course, I would probably want to index the state slot of zip-code
> because there are tens of thousands of zip codes and I wouldn't want
> to linearly traverse them, but I just wanted to illustrate the problem
> to get some additional feedback (the overhead of maintaining a
> secondary index on state wouldn't matter too much to me because
> changes to this class/objects are very rare but access is much more
> frequent)
>
> 2) Maybe this is a totally different issue and mainly caused by my
> lisp ignorance:
>
> If I have:
>
> (defparameter *s1* (get-instances-by-value 'state 'abbr "FL"))
> (defparameter *s2* (get-instances-by-value 'state 'abbr "NY"))
> (defparameter *z1* (get-instances-by-value 'zip-code 'zip "33015"))
> (defparameter *z2* (get-instances-by-value 'zip-code 'zip "13605"))
> (defparameter *z3* (get-instances-by-value 'zip-code 'zip "33160"))
>
> and I want to remove the association of zip code 33160 from the "FL"
> state object, I would think all I have to do is:
>
> (setf (state-of *z3*) nil)
First problem here is that get-instances (note the plural) returns a
list. However that will work. You orphan the zip code by removing
it's reference to a state. However there is a singular function that
returns the first instance or nil.
(defparameter *z3* (get-instance-by-value 'zip-code 'zip "13605)))
(setf (state-of *z3*) nil)
So you had the right idea but just missed that detail.
>
> However, when I do so, I get this error message:
>
> There is no applicable method for the generic function
> #<STANDARD-GENERIC-FUNCTION (SETF STATE-OF) (1)>
> when called with arguments
> (NIL
> (Zip (zip, city, county, state) = (33160, Sunny Isles Beach, Dade,
> State (abbr, name) = (FL, Florida)))).
> [Condition of type SIMPLE-ERROR]
>
> Restarts:
> 0: [ABORT-REQUEST] Abort handling SLIME request.
> 1: [ABORT] Exit debugger, returning to top level.
>
> Backtrace:
> 0: ((SB-PCL::FAST-METHOD NO-APPLICABLE-METHOD (T)) #<unavailable
> argument> #<unavailable argument> #<STANDARD-GENERIC-FUNCTION (SETF
> STATE-OF) (1)> (NIL (Zip (zip, city, county, state) = (33160, Sunny
> Isles Beach, Dade, State (abbr, name) = (FL, Florida)))))
> 1: ((SB-PCL::FAST-METHOD NO-APPLICABLE-METHOD (T)) #<unavailable
> argument> #<unavailable argument> #<STANDARD-GENERIC-FUNCTION (SETF
> STATE-OF) (1)> (NIL (Zip (zip, city, county, state) = (33160, Sunny
> Isles Beach, Dade, State (abbr, name) = (FL, Florida)))))
> 2: (SB-INT:EVAL-IN-LEXENV (SETF (STATE-OF *Z3*) NIL) #<NULL-LEXENV>)
> 3: (SWANK::EVAL-REGION "(setf (state-of *z3*) nil)" T)
>
> 3) So, going back to the previous questions in the email, if I wanted
> to permanently remove zip code "33015", how would I go about it?
>
> Thanks again and thanks for the patience.
>
> - Daniel
>
> On Nov 14, 2006, at 9:04 AM, Ian Eslick wrote:
>
>> Persistent classes in the current model aren't easy to fully delete -
>> you can only make the unreachable by having no reference to them
>> reachable from the controller or class roots. You can drop an object
>> from the index and there is a way to delete the object from the main
>> system BTree - but until 4.4 you couldn't reclaim that space (unless it
>> happened to be reused opportunistically). In 4.4 you can compact the
>> DB, but elephant does not take advantage of this yet.
>>
>> Ideally there would be an automated way to 'migrate' which is a
>> stop-and-copy model of GC - everything reachable from the controller and
>> class roots gets copied, anything that isn't reachable stays in the old
>> DB. This compacts and cleans the DB. I hope that we'll clean up the
>> model of space reclamation and provide something akin to GC in the not
>> too distant future. It's not a high priority in large part because
>> on-disk space has little implication on in-memory space and disk is ~
>> free. (Although I do suffer from too many backup copies of my 6GB DB -
>> fortunately I just upgraded my computer and doubled my hard drive space
>> so I'm OK for a awhile longer!)
>>
>> Ian
>>
>> Pierre THIERRY wrote:
>>> Scribit Daniel Salama dies 13/11/2006 hora 21:00:
>>>
>>>> So, if I make my class persistent, it's persistent... period! I don't
>>>> need to add it to a collection or to the root.
>>>>
>>>
>>> Well, I did not know that before that discussion. I think it's not
>>> clearly indicated in the docs...
>>>
>>> And then I wonder: if I use persistent classes, how do I remove an
>>> object from the store?
>>>
>>> Curiously,
>>> Nowhere man
>>>
>>> ------------------------------------------------------------------------
>>>
>>>
>>> _______________________________________________
>>> elephant-devel site list
>>> elephant-devel at common-lisp.net
>>> http://common-lisp.net/mailman/listinfo/elephant-devel
>> _______________________________________________
>> 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