Prevalence Is Acid

Prevayler claims to support ACID (AtomicConsistentIsolatedDurable) transactions.

Specifically, see this post by KlausWuestefeld, founder of Prevayler:

http://www.theserverside.com/news/thread.tss?thread_id=30735#151813

From the AtomicConsistentIsolatedDurable page:

Prevayler claims ACID (AtomicConsistentIsolatedDurable), and no need for transactions, rollback, etc. The entire rest of the database world universally disagrees with this ACID claim and thinks they don't use the same terminology as everyone, and possibly don't understand the rest of the world's terminology. But they are fast. -- DougMerritt

What an honour. I finally meet the spokesperson of the entire database world. Prevayler does have transactions (which I believe to be necessary) and rollback (which I believe to be unnecessary but useful in some situations). -- KlausWuestefeld

Transactions without rollback sounds like a contradiction in terms. The point of transactions isn't just that a transaction operates on a consistent view of the data - it's that if something goes wrong in mid-transaction, it can be rolled back and have no effect on the data.

There are mechanisms for 'having no effect on the data' that don't involve rollback, such as keeping a 'consistent view' of the data per transaction (used, for example, by ClojureLanguages implementation of SoftwareTransactionalMemory). Such systems abort and fail without ever overwriting the primary copy of the data, thus nothing ever needs to be rolled back in the event of failure - at worst, they need to roll forward, in the event of a communications failure during a commit (ThreePhaseCommit?).

The building blocks of prevalence - mutual exclusion, checkpoints and write-ahead logging - are a sufficient foundation to provide AtomicConsistentIsolatedDurable execution. You can implement rollback by performing recovery: restore your last checkpoint and then roll forward through the write-ahead log. HSQLDB appears to me to be a database that uses prevalence as an implementation technique; its data file is simply a SQL script consisting of a checkpoint (a bunch of CREATE TABLE/INSERT) and write-ahead log (any additional DML since the last checkpoint is appended to the file, except for pure SELECTs). -- JeffreyHantin


Prevayler has "roll forward." ...similar, in a sense, to the recovery from transaction log work conventional relational databases do when they restart.

Should Prevayler crash, on restart it will restore memory from the "last full backup" (IE: the last time everything was serialized from memory to a file, and then rerun all the transactions that happened since then. This will bring it "up to date."

From the AtomicConsistentIsolatedDurable page: Prevayler transactions are Atomic, but only if they don't throw exceptions. As I understand it, the current release runs (by default) with two copies of your data in memory; it "pre-runs" your transactions on the first copy, to verify that they don't throw exceptions, and then it runs them on the second, the "gold copy." Presumably, the "pre-run" copy can be copied again from the "gold copy" quickly, should a transaction fail.

Prevayler transactions are Consistent, to the extent that your implementation language and application code enforce your declared data integrity constraints. The Java and C# compilers and runtime environments enforce that you can't set a pointer to an object of the wrong type, enforcing the ReferentialIntegrity constraint (http://en.wikipedia.org/wiki/Referential_Integrity). In ObjectOriented programs, field constraints can be enforced with consistent use of "setter" methods. Relational database implementations typically provide a more extensive set of declarative integrity constraints, but still not everything needed to enforce all reasonably definable business rules.

Prevayler transactions are Isolated - from other transactions running concurrently - because Prevayler doesn't do that. Prevayler runs transactions sequentially, one at a time. So it doesn't have locking, contention, and interaction problems between transactions. Thus Prevalyer implements only the strongest form of transaction isolation defined in the ANSI/ISO SQL standard: SERIALIZABLE. However, achieving serializability by actually serializing all transactions limits Prevayler to the speed of a single CPU core.

Prevayler transactions are Durable because the system starts at a known state, stored on disk, and writes every transaction to disk before executing it. Because transaction code must (by definition in a Prevayler system) be deterministic, Prevayler can always restore system state from disk by rerunning the logged transactions.


Do you mean the transactions are ACID for the object memory store? Or ACID for streaming to the journal? The first one is what one would be looking for especially for Atomicity and Isolation.

Without the logs / transaction journals, the ObjectPrevalence? approach can't be Durable. For transactions to be Durable, you need some recovery mechanism that will survive power outages, program crashes, etc.

Prevayler logs all transactions to disk before running them. In the event of system failure, it can rerun the transactions. This is how it achieves Durablity.


When I rollback a transaction will it rollback all the objects in the memory store and are the updates to the object memory store in one transaction isolated from the update in another transaction. For example, in my transaction I don't want to see the updates created by another transaction until they are committed or rolledback. Right?

Heh. You probably don't ever want to see the updates created by another transaction after they've been rolled back. As far as seeing updates from other transactions prior to them being committed? Prevalence makes it a non-issue: it prevents concurrent transactions by the simple mechanism of serializing them. Thus, you'll never see the updates from another transaction until after that transaction has fully committed - your transaction won't even start before the other transaction has fully committed.

In the more general sense of ACID semantics with concurrency, it is actually okay for you to see state updates from other transactions before those other transactions fully commit... so long as they DO, eventually, fully commit. In optimistic systems that support concurrent transactions, that is often exactly what happens. However, it does mean that your final 'commit' waits for the other transaction to commit AND that your transaction fails if the other transaction either fails or updates the same cell again to a different value (updating the same cell twice in one transaction) or reads/updates another cell your transaction read before it was updated... but, even with those complications, it can work surprisingly well in practice when it comes to improving concurrency - especially for short or 'small' transactions. Due to use of fewer or even no cross-cell locks, and eliminated risk of deadlock, optimistic transactions are about the only very practical approach for distributed cells (e.g. distributed databases, distributed cache management, etc.). Even for the worst cases, where one transaction is spending a lot of time updating the same cell repeatedly then failing, it is possible (with a flexible transaction manager) for your policies to become 'somewhat less' optimistic (e.g. forcing a priority ordering of transactions) after a transaction you were counting on succeeding has already failed and restarted once.

Prevayler avoids concurrency problems by avoiding concurrency: Only one transaction runs at a time. This is less of a problem than you might think, because all data is in memory. This avoids I/O latency problems, eliminating the need to run transactions concurrently.

Caveats:

Certainly assertions to the extent to which Prevayler and most RelationalDatabase implementations enforce the "Consistent" attribute of ACID (AtomicConsistentIsolatedDurable) transactions is bound to be controversial.

Let's consider KlausWuestefeld's statement, "Prevayler does not provide your transactions with Consistency nor does any database server. It is always up to the application to make its transactions Consistent, even with database servers." From http://www.theserverside.com/news/thread.tss?thread_id=30735#151813

See also http://en.wikipedia.org/wiki/Integrity_constraints - Wikipedia's definition of Consistency in ACID.

Constraints that may be enforced or easy to implement in a Prevayler environment: Constraints that are not implemented by most RelationalDatabase implementations: Certainly, Prevayler (and its host language) enforcement of independently defined Constraints is weaker than in the relational model. It's present, but weaker. And RelationalDatabase support for Constraint enforcment has gotten stronger, particularly with the ANSI/ISO SQL 92 standard. So while it's reasonable to say that PrevalenceIsAcid, I think that KlausWuestefeld's comment about RelationalDatabases failing to enforce consistency constraints contains some truth, but is a little over the top. -- JeffGrigg

EditText of this page (last edited July 9, 2010) or FindPage with title or text search