A simple persistent store

ChangeSafe contains a simple persistent store.  The code is here.

To get an idea of how this works, start with tests.lsp

First, when  open-persistent-store is called, the persistent store is (obviously) opened.  If the store doesn't exist, it is created.  It is easier to write code with the assumption that there is always a persistent state that can be updated rather than having special code deal with a once only initialization.

All interaction with the contents of the store takes place within an atomic transaction.  When the transaction ends, either all the updates to the store take place, or none do.  This allows the programmer to briefly ignore consistency requirements during computation so long as the end result is consistent. The interface is fairly simple:

call-with-transaction pstore transaction-type reason receiver

pstore - a persistent store
transaction-type - one of :read-only, :read-write, or :read-cons
reason - a human readable string describing the purpose of the transaction
receiver - a procedure of one argument (the transaction object) which is invoked during the transaction

In the usual, expected case, the receiver runs, possibly makes updates to the store, and returns a value. When the receiver returns, the transaction commits (finishes) and the changes to the store are applied atomically.

In the less usual case, the transaction may be aborted.  In this case, no (detectable) changes are made to the store.

The decision to commit or abort is usually made implicitly:  if the receiver procedure returns normally, the transaction commits, if it performs a non-local exit, via a throw or through error recovery, the transaction aborts.  However, the programmer can explicitly cause the transaction to commit or abort through a call to transaction/commit or transaction/abort.

The transaction-type indicates what kind of transaction is to be performed.  Naturally :read-write is used to update the store and :read-only is used if no update is necessary.  :read-cons is for the case of a transaction that only creates new persistent objects and does not change existing objects.  The implementation ensures that transactions are isolated (transaction in progress are not visible to each other) and serializable (committed transactions can be placed in a consistent order even if executed in parallel).  :read-only transactions only have to be consistent throughout execution, so many can (in theory) be run in parallel.  :read-write transactions can be run in parallel only if they do not interfere with each other.  :read-cons transactions are a special case of :read-write.  Since new objects are not visible outside the transaction until the transaction commits, there can be no interference between multiple :read-cons transactions. (Support for :read-cons is sketchy, though.  Although there should be no interference, each transaction must issue unique object ids and thus they do interfere implicitly.  There are ways to deal with this, but I didn't implement them.)

The reason is simply a string that is recorded along with the transaction.  This is to help the user understand the sequence of transactions when examining the history of the store.

The receiver is invoked on an object representing the transaction.  It is often ignored because the implicit commit or abort behavior is usually used, but the argument is there if desired.

During the transaction, the special variable *current-transaction* is bound to the transaction object.

So let's look at some code:

(let ((store (persistent-store/open pathname))
       id
       vid
       (object1 '(this is a list))
       (object2 #(this is a vector))
       (object3 (list 1.0d0 -1.0d0 0.125d0 -0.125d0 1024.0d0 -1024.0d0 .3d0 -.3d0))
       (object4 (list #x87654321 #x12345678 1 -1 2147483647 -2147483648
                      #*101010101010101010101010101
                      #*100000000000000000000000000
                      #*000000000000000000000000001))
       o1id
       o2id
       o3id
       o4id)
   (call-with-transaction
    store :read-write "Save some objects."
    (lambda (transaction)
      (declare (ignore transaction))
      (setf o1id (persistent-object/save object1 store)
            o2id (persistent-object/save object2 store)
            o3id (persistent-object/save object3 store)
            o4id (persistent-object/save object4 store)))))

This code saves some simple lisp objects to the store.  persistent-object/save writes the object to the store and returns a unique integer (the object-id). Obviously we'll want a :read-write (or :read-cons) transaction.

 Later on, we call

       (call-with-transaction
        store :read-only "Verify objects."
        (lambda (transaction)
          (declare (ignore transaction))
          (verify
           (verify-one-return-value (verify-value-equal object1))
           (persistent-object/find store o1id))
          (verify
           (verify-one-return-value (verify-value-equalp object2))
           (persistent-object/find store o2id))
          (verify
           (verify-one-return-value (verify-value-equal object3))
           (persistent-object/find store o3id))
          (verify
           (verify-one-return-value (verify-value-equalp object4))
           (persistent-object/find store o4id))))

persistent-object/find takes the integer returned by persistent-object/save and returns the object.  In this case we use a :read-only transaction, but we would use :read-write if we were going to modify any objects.

One has to be careful about equality.  The object returned by persistent-object/find may not be EQ to the object saved. It would be very difficult to implement this in general, and it isn't needed in most cases. Symbols are treated specially to preserve EQ-ness.

How it works

The persistent store contains a serialized representation of the objects and an object-map, which holds the mapping from the integer object ids to the representation. (The node in the object map contains the address in the file where the object has been serialized.  When the object is deserialized, it is cached.)  The object-map itself is a persistent object and is itself serialized.  When a transaction commits, a record is appended to the store that contains the root node of the object-map.

There are many implementation strategies.  The one that I chose was driven by a number of considerations:

• It had to be easy to reason about.  This is critical because the correctness of the entire product depends on the correct use of the store, and this is a very complicated product.
• It had to be easy to implement the basic functionality.  I only have so much time and energy.
• It had to be adaptable to a more sophisticated and higher-performance implementation.

But there are some special properties about the intended use of the store.  The bulk of the storage is expected to be strings, simple structures, and change records.  For performance, it is desirable that disk access is minimized.  Empirically, it is the case that most of the change records are consulted at some point during operation.  The store is therefore used in "prevalence" mode:  the entire contents are deserialized when the store is opened and kept in memory.  Read operations are fast because they do not have to access the disk.

Additionally, few persistent objects are truly modified.  When the programmer changes an object, a change record is created and appended to the store, but the original object is unmodified.  This naturally provides the "temporal" aspect of the store:  by truncating the set of change records we can "turn back time" to any desired point.  Because the primitive objects are not mutated, there is no need to synchronize transactions with a "master copy", thus the store can be implemented as a "log-only" (or append only) structure.

A log-only store is fairly easy to implement.  At transaction commit time a special commit record is appended to the log.  When the store is recovered after being shutdown or after a crash, we look for the most recent commit record and recover from there.  This means that we can pretty much stuff anything we want on to the end of the log provided that the commit records are correct.  There is actually no difference at all between recovery from a crash and recovery from a shutdown.  During development of other parts of ChangeSafe I often crashed the database. Not once did I encounter a recovery problem.

Persisting CLOS objects is challenging.  I will address that in the next post.