CL-PREVALENCE

CL-PREVALENCE is an implementation of Object Prevalence for Common Lisp.
It was written by and is being maintained by Sven Van Caekenberghe.
CL-PREVALENCE is using S-XML for the XML serialization
protocol (there is also a more Lisp-like s-expression-based serialization protocol).

Object Prevalence is a simple but interesting concept first proposed by Klaus Wuestefeld in 2001.
IBM developerWorks has a reasonable
Introduction to Object Prevalence article.
The main Java implementation is called Prevayler,
with a (chaotic) wiki site with lots of information and discussions.
The following academic paper seems to describe the most essential features of Object Prevalence, without naming it as such:
A Simple and Efficient Implementation for Small Databases
by Birrell, Jones, and Wobber [1987].
Basically, the idea is this:

Most databases are only a couple of hundreds of megabytes big, often even less.

Most computers can easily take a couple of hundreds of megabytes of data in RAM, big servers can hold many gigabytes.

Mapping objects to databases is at least tedious and time consuming, but often also complex and error prone.

Let's throw away the database and just consider the domain model objects as the database.

Let's make sure we can serialize and deserialize our objects to and from a some presistent medium such as a file system.

If we store our complete set of domain model objects to a persistent medium we create a snapshot.

We query by using the data structure manipulation functionality of our programming language, running from RAM, queries will be extremely fast.

Let's agree to only change our object model using transaction objects that combine the data and the functionality to execute the transaction.

In order to preserve the ACID properties of our system, we log each transaction to some persistent medium by serializing it after we execute it. The is called the transaction log.

When the system goes down (intentionally or unintentionally) we restore its latest state by first reading in the latest snapshot and by re-executing each transaction from the transaction log.

Transactions must be deterministic and re-entrant (so they also need to record the current time if necessary).

In a multi-threaded system, transactions are globally serialized.

That is all there is to the concept of object prevalence. Here are some more details as well as some advantages and limitations:

A good implementation on a modern machine can achieve thousands of transactions per second, and recover them at about the same speed.

Transactions must be short because they block the system - since everything is in RAM this is not a problem.

Queries that need to see a completely consistent system state must also block on the system - other less critical queries could run in parallel.

It is practical for a transaction to first check its preconditions, throw an error if necessary, and to only modify the system when everything is consistent. During a transaction you are the sole active thread. Queries are as fast as they can get. In this implementation transactions are logged after succesful execution.

In this implementation there is an option to do a rollback (by doing a system restore) when an unexpected error occurs during transaction execution. You can specifiy that a condition doesn't need a rollback when it occurs inside a transaction by implementing the initiates-rollback to return false (or by using the no-rollback-error condition or inheriting from it).

Long running transactions are an open question.

Application server techniques are used to offer multiple clients access to the same prevalence system.

We can easily do replication (and query load balancing) by distributing the master transaction log stream to replica's that can host queries, execute backups (snapshots) or serve as hot fail-over. This implementation does not yet contain replication.

This code was written by Sven Van Caekenberghe.

Download

The latest version of cl-prevalence is maintained in a
Mercurial repository.
An interim release tarball is available:
3.5 release.
This is the currently recommended version.