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

"Prevayler provides your transactions with Atomicity and Durability. That is pretty evident to most people."
"Prevayler also provides Isolation through strict sequencing of all your transactions and, optionally, of all your queries. [...]"
"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 the AtomicConsistentIsolatedDurable page:

Atomic = all changes are made (commit), or none (rollback).
Consistent = system enforces declared integrity constraints
Isolated = independent of concurrent transactions.
Durable = committed changes make permanent changes to the data.

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:

Atomic = all changes are made (commit), or none (rollback).
Consistent = system enforces declared integrity constraints
Isolated = independent of concurrent transactions.
Durable = committed changes make permanent changes to the data.

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:

Page faults stall everything in the Prevayler server. This can be a serious problem if you don't have sufficient RAM.
Rollbacks are expensive. You should code your transactions, to the best of your ability, to not need them. Do this by validating the data before changing anything.

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:

The equivalent of ReferentialIntegrity constraints are enforced in modern languages with a combination of strong type checking and automatic memory management.
- Strong type checking prevents programmers from making a "foreign key"-like reference to an object of an incompatible type. In some languages, like Java and safe C#, the language strongly enforces these constraints. In some languages, like C, C++, and type unsafe C# code, the language generally prevents accidental references to incorrect types, but gives the programmer the option to override this protection. Weakly typed languages allow references to incompatible types, but report the errors in a systematic way at runtime, when unsupported operations are attempted.
- When automated memory management (IE: GarbageCollection) is used, and manual memory management (IE: free & dispose calls) is not used, then invalid references to released (IE: deleted) objects will not occur. This would be the equivalent of "delete" referential integrity; preventing the deletion of objects/records referenced by active objects/records.
- In an ObjectOriented program, there can be issues of references to objects that have not been fully initialized. This can be addressed by programming conventions, such as relying more heavily on constructors than on setter initialization.
- In an ObjectOriented program, there can be issues of references to objects who's resources have been released. This generally won't be an issue in the Prevayler environment, because objects holding external system state aren't business objects. Such objects shouldn't be allowed in the Prevayler managed system state.
The equivalent of EntityIntegrity? is accomplished by using different operational definitions: Programs don't generally need to rely on unique field values to identify unique object instances within each set of all existing instances of that type, because running programs typically hold direct references to the address of each instance in memory. In fact, only a few programming languages, like Smalltalk, offer the programmer the ability to find all active instances of a given type. In object-oriented programs, object identity is defined by the instance's address. No rules about field values are needed.
- There are cases where we want different object instances to be treated as the same, such as multiple instances of the string "Jeff Grigg". We have widely adopted conventions for dealing with that issue, such as use of the "equals" method. Some languages have special syntax or methods to make reference to unique string instances too.
Domain Constraints prevent the entry of invalid values in columns or fields. Both databases and strongly typed programming languages have this feature. And if you wish to restrict the set of valid values further, the equivalent of database column constraints can be accomplished with checks in setter methods. Use of EnumeratedTypes, in a strictly typed language, can strongly enforce use of only a limited set of values. Some languages, like the PascalLanguage, even allow direct specification of limited numeric ranges as data types.

Constraints that are not implemented by most RelationalDatabase implementations:

In practice, taking full advantage of all the constraint declarations possible in the latest ANSI/ISO SQL standards and the latest vendor products has proven beyond the knowledge and ability of most software development organizations.
- It's common to find database schemas defining all non-primary-key columns as nullable, even when null values in many those columns would cause their systems to fail.
- It's common to find database schemas lacking most obvious referential integrity constraints.
- It's quite uncommon to find database schemas leveraging the latest ANSI/ISO 92 standard deferred constraints and assertion constraints - both of which are needed to address the most common failings of traditional SQL constraints, such as requiring that parent tables have children, or that the sum of all DoubleEntryBookkeeping entries add up to zero.

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