Mix in a little CLOS

The obvious idea here is to make CLOS objects where the slots are implemented as versioned value objects. Then we override slot-value-using-class. You might consider this a stupid CLOS trick. You could just as well establish an abstraction layer through other means, but the point is to create an understandable abstraction model. It is easy to understand what is going to happen if we override slot-value-using-class.

We use the MOP to create a new kind of slot so that we can compose values on the fly when the programmer calls slot-value-using-class. We also override (setf slot-value-using-class) so that it calls the "diff" computing code. Again, the point is to make it easy to understand what is happening.

The end result is the versioned-standard-object. An instance of a versioned-standard-object (or any of it's inheritors, naturally), has all its slots implemented versioned value objects. The programmer should specify versioned-standard-class as the metaclass in the class definition.

(defclass test-class ()
  ((nvi-slot  :version-technique :nonlogged
              :accessor test-class/nvi-slot)
   (lnvi-slot :version-technique :logged
              :accessor test-class/lnvi-slot)
   (svi-slot  :version-technique :scalar
              :accessor test-class/svi-slot))
  (:metaclass versioned-standard-class)
  (:schema-version 0))

In this example, the test class has some of the different kinds of versioned values that are named by the version technique. A :nonlogged slot is the "escape mechanism". It's a fancy name for "Just turn off the versioning, and use this here value."

A :logged slot is less drastic. There's no versioning behavior, it's just a persistent slot, but we'll keep a list of the transactions that modified it.

Finally, the :scalar version technique is one where the last chronologically participating change has the value.

A versioned slot using the :composite-sequence uses a set of diffs to represent the versioned slot value, and these are composed as described in an earlier post.

(defclass test-cvi-class ()
  ((cvi-slot-a :version-technique :composite-sequence
               :accessor test-cvi-class/cvi-slot-a)
   (cvi-slot-b :version-technique :composite-sequence)
   (cvi-slot-c :version-technique :composite-sequence :initform nil))
  (:metaclass versioned-standard-class)
  (:schema-version 0))

Once this is working, we have what we need to bootstrap the rest of the versioned storage.

Putting things together

Ok, so we have audit records, a persistent store, and "diffs". Let's start putting them together. Naturally, we are going to keep the audit records in the persistent store, and we'll put the diffs in the audit records.

A versioned value is the abstraction we're aiming for. We're going to create a versioned value by combining the information held in the audit records. If the information is a set of insertion and deletion records, we combine them as I described in the previous posts.

What makes this interesting is that we can specify a subset of the audit records to participate in the construction of the value. We can extract the versioned value as it appeared at any point in time by specfying only those records that have a timestamp at or before that point. We can also synthesize interesting views by omitting some of the records.

We're going to store a lot of these versioned values and we'll use many of them every time we access the store. To get any kind of coherent view of the world, we want to use a single set of audit records when we view these values. But programmers, being who they are, won't want to think about this. So here's what we'll do: we already have transactions in order to talk to the store; we'll add a field to the transaction that specifies the audit records to be used during that transaction. Pretty simple. You want to look at the world as it was on July 4th, you start the transaction with those audit records dated July 4th or earlier and use that set for every versioned value that you want to look at. It would be crazy to look at some objects as if it were July 4th, but others as if it were December. (Heh, but on occasion....)

There is another reason we want to specify a set of audit records at the beginning of a transaction: we need to know the baseline that we compute our diffs against. When we do a read/write transaction we're going to modify some of our versioned values. When the transaction ends, we need to compute the diffs of the things we modified. We compute the diffs relative to the view we established at the beginning of the transaction.

So we need to modify our audit records to record the basis set of records we use when we begin a transaction. We modify the transaction API to require the programmer to specify which basis set of records are to be used for the transaction and we use that basis set for computing the diffs at the end of read/write transactions.

There is an interesting side effect of this change. Suppose we have some way of attaching a label to the transactions, and some transactions only use label 'A' and others only use label 'B'. Further transaction using label 'A' only see diffs relative to prior 'A' versions, while the 'B' transactions only see the 'B' diffs. The result is that a single versioned value can hold two completely different histories.

Plus ça change

Let's start with a list:

'(a b c)

We change it:

'(a b c d)

We change the result:

'(0 a b c d)

etc.

'(0 a b c)

etc.

'(a b c)

and now a big change:

'(-1 0 1 a a1 b b1 c d e f)

At each step we compute the indels for that step. If we so desire, we can reconstruct any of the intermediate lists by starting at the beginning and applying the appropriate indels in order.

But what if we skip some? We end up with a mess. Each set of indels is computed relative to the application
of the prior indels. If an indel is omitted, the indices of the subsequent indels will be wrong.

To solve this, we have to change the representation of our sequence (that is, we won't be modifying a list).
Instead, we'll represent our sequence as an ordered set of list segments that we'll concatenate. Insertion is easy — just add a segment. Deletion is slightly harder because we don't want to cross segment boundaries.

Reconstruction of an intermediate list requires more work, but we gain flexibility. We can apply a subset of the insertions and deletions and still get a meaningful result. For example, the first change we made was to create a list with the three elements '(a b c). The second change appended a 'd'. What if we apply the second change but omit the first? We append a 'd' to an empty sequence and get '(d).

How about if we apply only change 3? That inserts a '0' at the beginning giving us '(0).

If we apply change 2 and 3, still omitting 1, we get '(0 d).

That last change is tricky. We've deleted the 'a and prepended '(-1 0 1 a a1), and deleted the 'c and inserted '(b1 c d e f). If we omit change 4 and 5 (which delete the leading 0 and trailing 'd) we'll get '(-1 0 1 a a1 0 b b1 c d e f d). We preserve the order between different insertion points, so the inserted 0 is always before the inserted 'd, but we resolve ambiguous insertions by placing the later insertions before the earlier ones if they are in the same place.

Optional Exercise 7 (quite hard): Implement this as well.

Let's start with a list:

'(a b c d e f g h i j)

We'll add some elements:

'(a b c d e f g h i j k l m n o)

Delete some:

'(a b c d e i j k l m n o)

Add some more:

'(x y z a b c d e i j k l m n o)

Maybe delete one:

'(x y z b c d e i j k l m n o)

We want to compare the original sequence with the end sequence and
summarize the difference with a set of "indels", which specify the
indexes at where elements were inserted or deleted:

(diff '(a b c d e f g h i j) '(x y z b c d e i j k l m n o))

(#S(INDEL
    :LEFT-SUBSEQ-START 0         ;; 'a'
    :LEFT-SUBSEQ-LIMIT 1
    :RIGHT-SUBSEQ-START 0        ;; 'x y z'
    :RIGHT-SUBSEQ-LIMIT 3)
 #S(INDEL
    :LEFT-SUBSEQ-START 5         ;; 'f g h'
    :LEFT-SUBSEQ-LIMIT 8
    :RIGHT-SUBSEQ-START 7        ;; nothing
    :RIGHT-SUBSEQ-LIMIT 7)
 #S(INDEL
    :LEFT-SUBSEQ-START 10        ;; nothing
    :LEFT-SUBSEQ-LIMIT 10
    :RIGHT-SUBSEQ-START 9        ;; 'k l m n o'
    :RIGHT-SUBSEQ-LIMIT 14))

Exercise 6 (hard): Implement this.

For an extreme challenge, implement this in a way that is not hopelessly inefficient.

A bit harder

The last few exercises have been easy.  These will be intermediate.

So far, we've been using the integer serial numbers to refer to audit records when we don't have the record itself.  The record can be read and written in a transaction, but outside the transaction we need a non-persistent object to act as a name.  The problem with integers is that they aren't typed: whatever the number 42 means in one context is unlikely to be relevant in another.  The second problem is that we are deriving the integers from an underlying implementation artefact.  The number 42 just identifies an object to most of the code, but it derives from an index into a vector.  If we change how the number is generated, then any numbers we already know about would have to change as well.

We need an external naming scheme so we can refer to the audit records in a repository.

Exercise 5:

1. Have a required "name" argument when creating a repository.  The name should be immutable and you should be able to access the name without a transaction.
2. Define an identifier object.
   

   (defstruct (distributed-identifier
               (:conc-name did/)
               (:constructor %make-distributed-identifier (domain repository class numeric-id))
               (:copier nil)
               (:predicate distributed-identifier?))
     "DIDs are interned, so you can use EQ to test for equality.  However, you should
      never modify the slots in a DID."
   
     (domain ""     :read-only t :type string)
     (repository "" :read-only t :type string)
     (class nil     :read-only t :type (or null keyword))
     (numeric-id 0  :read-only t :type non-negative-integer))
   

   You can skip the domain element for now, but the other fields are needed.
   
3. Define a printer for a distributed-identifier so they print like this: [test-repository.AUDIT-RECORD.22] the name, class, and numeric id are printed with periods between them.
4. Define a parser that can read the fields out of a string.
5. Hook up the parser to the reader so that programmers can use the square bracket notation as a literal in a program.
6. Intern these objects in a weak hash table.  We want to be able to use EQ to test these. So typing (eq [test-repository.AUDIT-RECORD.22] [test-repository.AUDIT-RECORD.22]) will return true. If two distributed-identifiers print the same way, then they refer to the same object and they should be EQ.
7. Add a mapping table to the repository for the audit records.  You want it so that when an audit record is newly created it will have a new identifier. You'll want to decouple the assignment of the audit-record serial number from the assignment of the numeric ID in the distributed-identifier.  This is so we can import audit-records from other repositories.
   
   
   Consider [test-repository.AUDIT-RECORD.22]. It is the twenty-second audit record created by the test repository, but it is not necessarily at the twenty-second offset in the repository's table of audit-records. It could be, for example, at location 165. The mapping table gives the location. If a new audit-record is created, say at location 166, a new entry in the mapping table will map [test-repository.AUDIT-RECORD.23] to location 166.
   
   The mapping table will be persistent, and thus require a transaction to read.

Fairly easy

The prior post had some easy exercises.  This is easy, too.

Every audit record in a repository has a unique serial number (relative to the repository).  We want a way to represent sets of serial numbers.

Exercise 4:  Implement these:

Constructors:

• bitmap->serial-number-set repository vector-1b
• range->serial-number-set repository start end
  Start is inclusive, end is exclusive.
• list->serial-number-set repository list

Selectors and predicates:

• serial-number-set? object
• serial-number-set/repository serial-number-set
• serial-number-set/empty? serial-number-set
• serial-number-set/equal? left-serial-number-set right-serial-number-set
• serial-number-set/member? serial-number-set serial-number
• serial-number-set->bitmap serial-number-set

These return new sets rather than mutate the old ones:

• serial-number-set/adjoin serial-number-set serial-number
• serial-number-set/remove serial-number-set serial-number
• serial-number-set/union left-serial-number-set right-serial-number-set
• serial-number-set/exclusive-or left-serial-number-set right-serial-number-set
• serial-number-set/intersection left-serial-number-set right-serial-number-set

Two more:

• serial-number-set/intersaction? left-serial-number-set right-serial-number-set
  Returns true if the intersection is not empty. Ought to be faster than (serial-number-set/empty? (serial-number/intersection left right))
• serial-number-set/last-serial-number serial-number-set
  Returns the largest serial number in the set.
  
  

We'll use serial numbers and serial-number-sets so we can refer to audit-records and sets of audit-records without needing the records themselves.  We can only get to the records within a transaction, but we can refer to them by serial number outside of a transaction.

Fun with Audit Trails!

Gotta change direction here.  It's getting boring.  Let's implement an audit trail!  How hard could it be? We'll make an audit trail out of audit records.  Pick your favorite language and try this.

Exercise 1:  Implement an audit record.  Make sure it has these features:

• a timestamp of when the record was created
• a user-id to tell us who created the record
• a reason why in the form of human readable text
  

• immutable, including transitively reachable subobjects
• Malformed records cannot be created.  Automatically set the timestamp so it cannot be forged.

Now we have to keep them somewhere safe, and get them back on occasion.

Exercise 2a: Make a repository with some sort of stable storage for a backing store, like a file.

Exercise 2b:  When creating an audit record, log it to stable storage. Make the repository be a required argument for creation of an audit record.  Log the record in the repository, but don't store info about the repository itself in the record.  The record doesn't have to know where it lives.

Exercise 2c:  Have a way to load all the audit records back in from stable storage.  Intern the audit records so re-loading is idempotent and eq-ness is preserved.

Exercise 3:  Implement random access to a repository's audit log (indexed by integer)

These are all very easy.  Don't worry, I'll make it harder.