Lisp

[2026-07-24 Fri]

• tons of useful documentation in the doc/ subdir

one thing I haven't thought much about is how and when to initialize the 'stored index' containing an ordered collection of lisp values - figure out 'warm boot'.

The use of persistent objects makes coding concise, convenient, and powerful, and makes persistence almost invisible to the programmer. However, Elephant also allows the same basic data dictionary of key/value retrieval that BerkeleyDB provides.

(in our case RDB)

While Elephant can use either RDBMSs or Berkeley DB as a data store, the model it supports is that of objects stored in persistent indices. Unlike systems such as Hibernate for Java, the user does not need to construct or worry about a mapping from the object space into the database. Elephant relies on LISP rather than SQL for its data manipulation language. Elephant is designed to be a simple and convenient tool for the programmer.

Concepts:

• store controller (store)
• persistent sets (psets)
• Btrees - sorted order persistent KV abstraction
• stored values - most lisp values including standard objects/arrays, can be used as either key or value in a btree
• persistent objects - objects where most slot values are stored in the data store and IO performed on slot access. Storing a persistent object in a btree only store a reference for object identity.
• object indexing - the ability to lookup and sort objects by their slot values rather than by explicit inclusion in a collection.
• transactions - dx for executing operations on objects or collects (transaction/txn)

Basic operation is OPEN-STORE with a spec (cons where car is a backend kw), do stuff, then CLOSE-STORE. Alternatively WITH-OPEN-STORE.

What values live between lisp sessions is called liveness. Liveness in a store is determined by whether the value can be reached from the root of the store. The root is a special BTree in which other BTrees and lisp values can be stored. This BTree has a special interface through the store controller. (There is a second root BTree called the class root which will be discussed later.)

use ADD-TO-ROOT to put something into the root object and GET-FROM-ROOT to retrieve it. See also ROOT-EXISTSP, REMOVE-FROM-ROOT, MAP-ROOT. The root object itself can be accessed from the store itself.

important notes:

'This will affect all aggregate types: objects, conses, hash-tables, et cetera.'

• Lisp identity can't be preserved - if you get an object from the index, store as a lisp variable and then get it again, the two objects won't be EQ.
• Nested aggregates are stored in one buffer
• Mutated substructure does not persist
• Serialization and deserialization can be costly
• Merge-conflicts in heavily multi-process/threaded situations
• persistent classes
  • serialized by their OID and class
  • slot values are store separately (and invisible to the user), keyed by OID and slot
  • loading (deserializing) a persistent class instantiates the object or finds it in a cache if it already exists.
  • the cache is a weak hash-table.
  • slot values are NOT loaded until you ask for them. persisted slots don't have space allocated for them because we read from the DB.
  • Changes persist immediately
  • serde of persistent classes is fast, much faster than ordinary clos objects.
  • do not suffer from merge conflicts
  • declares all slots be persistent by default - use :transient t for non-persistent.
  • class slots with :allocation :class are never persisted

Persistent classes may inherit from other classes. Slots inherited from persistent classes remain persistent. Transient slots and slots inherited from ordinary classes remain transient. Ordinary classes cannot inherit from persistent classes – otherwise persistent slots could not be stored!

to simulate a new lisp session: FLUSH-INSTANCE-CACHE

Using persistent objects has implications for the performance of your system. Note that the database is read every time you access a slot. This is a feature, not a bug, especially in concurrent situations: you want the most recent commits by other threads, right? This can be used as a weak form of IPC. But also note that in particular, if your slot value is not an immediate value or persistent object, reading will cons or freshly allocate storage for the value.

Gets are not an expensive operation; you can perform thousands to tens of thousands of primitive reads per second. However, if you're concerned, cache large values in memory and avoid writing them back to disk as long as you can.

• persistent collections
  • pset and btree are the solutions provided for the setf problem

Each provides persistent addition, deletion and mutation of elements, but the pset is a simple data structure that may be more efficient in memory and time than the more general btree.

The pset is also a very convenient data structure for enabling a persistent slot contain a collection that can be updated without deserializing and/or reserializing a list, array or hash table on every access.

The only difference is the api used to manipulate it. Instead of slot accessors, we use insert, remove, map and find.

There is one drawback to persistent sets and that is that they are not garbage collected. Over time, orphaned sets will eat up alot of disk space. Therefore you need to explicitly free the space or resort to more frequent uses of the migrate procedure to compact your database. The pset supports the drop-pset

However, given that persistent objects have the same explicit storage property, using psets to create collection slots is a nice match.

BTrees are collections of key-value pairs ordered by key with a log(N) random access time and a rich iteration mechanism. Like persistent sets, they solve all the collection problems of the prior sections. Every key-value pair is stored independently in Elephant just like persistent object slots.

The primary interface to btree objects is through get-value. You use setf get-value to store key-value pairs. This interface is very similar to gethash.

In addition to the hash-table like interface, btree stores pairs sorted by the lisp value of the key, lowest to highest. This is works well for numbers, strings, symbols and persistent objects, but due to serialization semantics may be strange for other values like arrays, lists, standard-objects, etc.

see MAP-BTREE

• indexing persistent classes

(defsclass foo () () (:index t))

Notice the class argument ``:index t''. This tells Elephant to store a reference to this class. Under the covers, there are a set of btrees that keep track of classes

GET-INSTANCES-BY-CLASS returns all created instances, or more efficiently for iteration MAP-CLASS

Elephant makes no guarantee about the ordering of class elements, so you cannot depend on the insertion ordering

If we want ordered elements.. use slot indices!

(defsclass foo () ((a :index t) (b :index t)))

get-instances-by-value will retrieve all instances that are equal to the value argument, with the equality relation defined by the database backend.

TODO: GET-INSTANCES-BY-RANGE

To map over duplicate values, use the :value keyword argument. To map by range, use the :start and :end arguments.

MAP-CLASS-INDEX

• Transactions
  • use WITH-TRANSACTION macro
  • no dynamic nesting and idempotent side-effects
  • to perform a group of transactions, use ENSURE-TRANSACTION for each unit, which will reuse an existing transaction if there is one.
  • the side effects of the body must be the same no matter how many times the body is executed

The best rule-of-thumb is to ensure that transaction bodies are purely functional as above, except for side effects to persistent objects and btrees.

If you really do need to execute side-effects into lisp memory, such as writes to transient slots, make sure they are idempotent and that other processes cannot read the written values until the transaction completes.

We cannot have infinitely sized transactions due to the finite size of the data store's memory cache. Large operations (such as loading data into a database) need to be split into a sequential set of smaller transactions. When dealing with persistent objects a good rule of thumb is to keep the number of objects touched in a transaction well under 1000.

on to the guide.. [2026-07-25 Sat]

• all lisp objects are stored by value
• native byte ordering

• Atomic Types

  • nil has it's own special tag in the serializer so it is easily

  identifiable. nil is an awkward value as it is also a boolean. The boolean value t is stored as the symbol 'T.

  • Bignums are broken into a sequence of fixnum-sized chunks and

  assembled by masking words onto the bignum. This is awfully expensive, but it's always correct and fully portable.

  • A rational is merely a ratio of two integers stored as fixnums or bignums.
  • A complex is a pair of floating point values, rationals or integers.
  • Standalone chars are represented by their char-code and are stored in 32-bit format to ensure that all lisps are stored correctly.
  • Symbols are stored as two strings, the package name and the symbol name in that package. When deserialized, the target package is searched for and the symbol is interned in that package.
• Aggregate Types
  • Cons is simply stored as a cons record containing two nested elements. Linear lists are not treated specially (i.e. no cdr-coding) by the serializer.
  • Arrays are stored as sequences of nested, serialized elements. The array parameters are also stored so that arrays with fill pointers, adjustable arrays can be stored and reconstructed. The only arrays that cannot be reproduced are displaced arrays, which are copied by value and reconstructed as standard arrays during deserialization.
  • Hash tables are stored as a sequence of key-value pairs, where the key and value can be any serializable value. On deserialization, the reconstructed key and value quantities are written incrementally into the hash table. The hash table does remember it's test, rehash size and threshold and it's total count. The final size of the new hash table is set to (* (/ size reshash-threshold) rehash-size).
  • Structure objects are serialized using the metaprotocol. Each slot where the value is bound is serialized by serializing the slot name and the value in sequence. The underlying lisp must support the struct-constructor method so that a new, empty instance of the structure can be created and then populated by the stored keys and values.
  • Instances of subclasses of standard-object are stored almost identically to structs. The type of the object is stored and the object slots with bound values are serialized as slotname-value pairs. To read an object of this type, the lisp image must have the class defined and it must have at least the slots that are stored on disk. There is no good method for schema evolution (redefining objects to have less slots) of ordinary classes.

After initialization of a stored object the following state has been created:

placeholder instance

in memory, storage for oid, spec, lisp instance data and transient slot values. mediates access to stored values, does not persist itself.

cached reference

weak reference to instance in the store object cache

memory references

a normal reference to the instance may be retained by the caller

database slot values

the data store contains the stored slot values that were initialized, indexed by the object id and slot name

database references

if placeholder instance is written to a stored slot, added to a btree, or the class is indexed, a reference to the instance was added to the data store. This reference consists of an OID and a class name. If this reference is reachable, then the stored object can be reconstructed using the :FROM-OID keyword argument.

If you manually create an object using an OID which already exists in the database, initargs to make-instance take precedence over existing values in the database, which in turn take precedence over any initforms defined in the class.

• LIFETIMES

The distributed nature of persistent instance storage results in some interesting behaviors, especially with respect to transient slots. The prior section detailed the state of the system after the original initialization of an object. The object can then be in a number of different states:

resident

the canonical state of an in-use stored object

unreferenced, unreclaimed

all memory refs dropped but placeholder hasn't been reclaimed. Weak pointer still exists in object cache. If a database ref is fetched, the cached value will be used.

Non-resident

The object only exists as reachable database refs and slot values. This is the state after GC of the placeholder.

Recreated

An intermediary state where a non-resident object is fetched from the data store and its placeholder must be recreated prior to the object entering residency state.

• when a ref is deserialized, its OID is used to lookup the object in the store object cache. If this fails the instance is created with a call such as:

  (make-instance 'sclass :from-oid 2000 :store *store*)
  

• :from-oid inhibits some make-instance behavior

A good policy is to initialize transient values using an :after method on initialize-instance. This allows you to initialize transient values using either system defaults or persistent slot values. That way you can ensure that the transient slots are always in a consistent state when accessed by the application, regardless of when the placeholder object was recreated.

In general, transient slots are a good place for intermediate values in a computation or to cache frequently read items to avoid deserialization overhead. indexed-btree is an example of this approach, an in-memory hash is cached in the transient slot for reads and writes are mirrored to a serialized hash in a persistent slot. The :after method just copies the persistent hash value to the transient slot.

Creating a set-valued slot:

(defsclass my-set ()
  ((set-slot :accessor set-slot :initform nil :set-valued t)))

see SET-INSERT, SET-LIST

• Association Slots

Assocation slots allow you to create relationships between objects in your system. In the following set of examples two classes are created, a 'job' class and a 'person' class. These classes are related in that each person can only be associated with one job, but a job might have multiple people associated with it. To capture this relationship in Elephant you can use Association slots.

You can enable/disable class indexing for an entire class. When you disable indexing all references to instances of that class are lost. If you re-enable class indexing only newly created classes will be stored in the class index. You can manually restore them by using find-class-index to get the clas index BTree if you have an alternate in-memory index.

You can add/remove a secondary index for a slot. So long as the class index remains, this can be done multiple times without losing any data.

There is also a facility for defining 'derived slots'. These can be non-slot parameters which are a function of the class's persistent slot values. For example you can use an index to keep an alternate representation available for fast indexing. If an object has an x,y coordinate, you could define a derived index for r,theta which stored references in polar coordinates. These would be ordered so you could iterate over a class-index to get objects in order of increasing radius from the origin or over a range of theta.

…

Thus, the question of if and how a given class should be indexed is very flexible and dynamic, and does not need to be determined at the beginning of your development. This represents the ability to ``late bind'' the decision of what to index.

In general, there is always a tradeoff: an indexed slot increases storage associated with that slot and slows down write operations. Reads however remain as fast as for unindexed persistent slots. The Elephant system makes it simple to choose where and when one wants to utilize this tradeoff.

• see also src/elephant/classindex-utils.lisp - documents tools for handling class redefs and polcies that should be used for synchronization.
• *default-indexed-class-sync-policy* values:
  • :class - class is master, indices are deleted for any slots no longer indexed
  • :db - db is master, class indexing annotations are updated so slots which satisfy class-indexedp-by-name are isomorphic to the existing indices in the db.
  • :union - expected result - updates the class to match any existing indices and creates new ones.
• BTrees
  • core data structure, Elephant directly exposes it
  • basic API is: get-value, remove-kv
  • Sorting is done first by primitive type (string, standard-class, array, etc) and then by value within that type. The type order and internal sorting constraint is:
    • Numbers - effectively coerced to double float and sorted relatively
    • strings - varwidth - width type sorted separately?? hmm
    • pathnames,symbols - sorted by string radix then lexically
    • aggregates sorted by type in following order then arbitrary: stored instance refs, cons, hash-table, standard objects, arrays, structs, then nil.
    • not GC'd (like ssets) - use drop-btree to delete all KV pairs and return storage - the OID used will not be recovered.
• Btree Cursors
  • used to traverse btrees one KV at a time
  • must be created inside a transaction - made with call to make-cursor method of btree. Make sure to close cursor when stack is unwound, best to use with-btree-cursor.
  • can duplicate cursors with cursor-duplicate - avoids overhead
  • two states: initialized or uninitialized
  • to initialize:
    • cursor-first or cursor-last
    • cursor-set or cursor-set-range
  • once initialized cursor can be incremented or decremented - O(1)
    • cursor-next or cursor-prev
  • can use cursors for side effects: cursor-put replace the value without incrementing and cursor-delete deletes the KV pair and becomes uninitialized.
• BTree Indexing
  • indexed-btree maintains a set of btree-index instances which provide alternative indexing algos.
  • Each index is itself a btree with values matched to the keys of the parent btree.
  • Index is created with add-index
  • important property of btree-index: allows duplicate keys. No dupes allowed in btree and indexed-btree.
  • index cursors are just like btree cursors except you can get the main btree value instead of the indexed valued. parallel set of operations - cursor-pnext for example returns (exists, key, primary-btree-value, index-value = primary-btree-key).

The big difference between btree cursors and index cursors is that indices can have duplicate key values. This means we have to choose between incrementing over elements, unique key-values or only within a duplicate segment. There are cursor operations for each:

• Simple move - standard btree ops and cursor-pnext/cursor-pprev
• Move to different KV (cursor-pnext-nodup and cursor-pprev-nodup)
• Move to next duplicate KV (cursor-pnext-dup and cursor-pprev-dup)
• after incrementing through a set of dupes the last NEXT operation returns nil indicating no more dupes - consequence is the cursor is uninitialized and needs to be reset.

Shared Resource Locks:

• store connection table
• instance cache
• circularity buffer pool for serializer
• static-streams for FFI (rw: is this needed?)

You can trace execute-transaction to see the sequence of calls that occur dynamically and detect where and how many transactions are and are not happening.

• Repository migration and upgrade (see tests migrate1-5)
  • single generic migrate function

It is assumed that typically migrate will be called on two repositories and all live objects (those reachable in the root or class-root) will be copied to the target repository via recursive calls to migrate for specific objects.

Migrate will not handle:

• circular lists
• Indexed classes only have their class index copied if you use the top level migration.
• one-time activity - should close the source store after validation
• cannot currently migrate a store that has more data than your main memory. (rw: we can probably fix this)
• OID equivalence is not maintained - can overload the migrate method to accomplish this

To customize migration overload a version of migrate to specialize on your specific persistent class type.

(defmethod migrate ((dst store-controller) (src my-class)))

In the body of this method you can call (call-next-method) to get a destination repository object with all the slots copied over to the target repository which you can then overwrite. To avoid the default persistent slot copying, bind the dynamic variable *inhibit-slot-writes* in your user method using with-inhibited-slot-copy a convenience macro.

• Performance is usually measured in transactions per second. Database reads are cheap.

All data written to the data store ends up in a BTree slot using a transaction. There are two databases, one for persistent slot values and one for btrees. The mapping of Elephant objects is quite simple.

Persistent slots are written to a btree using a unique key and the serialized value being written. The key is the oid of the persistent object concatenated to the serialized name of the slot being written. This ordering groups slots together on the disk