The CAP Theorem Is Not a Theorem

After reading the attempted proof of the CAP conjecture [Lynch], I have come to the same conclusion as Mark Burgess [Burgess]. He writes:

Brewer's original conjecture has not been proven with mathematical rigour -- indeed, the formulation in terms of C, A and P is too imprecise for that to happen. So the status of CAP as a theorem is something of an urban myth [...].

[...]

Also, as a piece of scientific work, the paper is somewhat difficult to understand today, because it builds on a very particular set of unstated assumptions, jargon and mode of thinking that was rooted in the time of its writing. Moreover, it provides no precise definitions of any of the quantities referred to, particularly the much-discussed "P" ("tolerance" of packet loss). Part of the problem is that the conjecture is about network fault tolerance, but it never models the network at all.

Despite this, CAP is not useless, quite the contrary. It has spawned numerous discussions on the limitations of the availability and consistency that distributed services can provide.

I would like to see more mathematical rigor in computers science in general and for databases in particular. Data storage is a field where mathematics can be truly helpful. More on that some other time.

[Lynch] Brewer's conjecture and the feasibility of consistent, available, partition-tolerant web services, Nancy Lynch and Seth Gilbert, ACM SIGACT News, Volume 33 Issue 2 (2002), pg. 51-59.

[Burgess] Deconstructing the `CAP theorem' for CM and DevOps, Mark Burgess, http://markburgess.org/blog_cap.html

"ACID" Does Not Make Sense

OK, that title is a bit provocative, but it seems to have caught your attention. A more sensible title would have been "A Critique of the ACID Properties".

Even though I have studied databases for some time, I have always had a problem with the commonly referenced ACID concept. It never really made sense to me. At least as four independent properties. So I decided to study the roots of it.

The Transaction Concept in [Haerder] and [Gray1]

"ACID" was first mentioned in [Haerder], 1983 (Principles of Transaction-Oriented Database Recovery). Let me quote:

Atomicity. It must be of the all-or-nothing-type described above, and the user must, whatever happens, know which state he or she is in.

Consistency. A transaction reaching its normal end (EOT, end of transaction), thereby committing its results, preserves the consistency of the database. In other words, each successful transaction by definition commits only legal results. This condition is necessary for the fourth property, durability.

Isolation. Events within a transaction must be hidden from other transactions running concurrently. If this were not the case, a transaction could not be reset to its beginning for the reasons sketched above. The techniques that achieve isolation are known as synchronization, and since Gray et al. [1976] there have been numerous contributions to this topic of database research [Kohler 1981].

Durability. Once a transaction has been completed and has committed its results to the database, the system must guarantee that these results survive any subsequent malfunctions. [...].

These four properties, atomicity, consistency, isolation, and durability (ACID), describe the major highlights of the transaction paradigm, which has influenced many aspects of development in database systems. We therefore consider the question of whether the transaction is supported by a particular system to be the ACID test of the system's quality.

The authors of [Haerder] says that the section quoted above relies on the concept of a transaction in [Gray1]. In that paper, Jim Gray writes: "The transaction concept derives from contract law". And further:

The transaction concept emerges with the following properties:

Consistency: the transaction must obey legal protocols.

Atomicity: either it happens or it does not; either all are bound by the contract or none are.

Durability: once a transaction is committed, it cannot be abrogated.

Haerder added "Isolation" to the previous three properties introduced by Gray.

Trying to make sense

Neither [Gray1] nor [Haerder], provide an exact definition of the transaction properties and I believe this was never the intention of the authors.

I have two main issues with the standard use of the term "ACID" as defined by [Haerder] (or Wikipedia).

1. The ACID properties are not well-defined. There are multiple interpretations. A more stringent formal definition would be useful. These properties should and can be defined with mathematical preciseness.
2. My preferred interpretation of "atomicity" would imply the "isolation" property.

I interpret the all-or-nothing notion of atomicity to mean that a reader of the database will see either all or none of the updates that a transaction makes to the database. Let's call this interpretation Atomic1.

The current text from Wikipedia on Atomicity says:

In an atomic transaction, a series of database operations either all occur, or nothing occurs. A guarantee of atomicity prevents updates to the database occurring only partially, which can cause greater problems than rejecting the whole series outright. In other words, atomicity means indivisibility and irreducibility.

The text says that either all operations occur or nothing occurs and that atomicity means indivisibility. To me, this wording imply isolation of transactions since a transaction cannot see the partial updates made by another transaction.

Another interpretation of atomicity (lets call it Atomic2) is that a transaction either completely survives a database crash or is completely ignored when the database restarts. While the database is running atomicity (Atomic2) means that eventually all updates of the transaction are visible to all readers or none of them is visible to any reader. However, while the transaction is running, readers may see uncommitted updates. With this interpretation of atomicity, the isolation property makes sense. We could then have transactions that have the atomicity property, but not necessarily the isolation property.

With the Atomic2 interpretation, the isolation property is meaningful and the ANSI SQL isolation levels are useful. However, there are multiple problems with those. See [Gray2]. The definitions of the isolation levels are ambiguous and and the set of isolation levels are biased towards pessimistic concurrency control (locking). These isolation levels are sometimes not useful for optimistic conconcurrency control.

The simplest solution would be if databases that claim to support transactions would always use the isolation level SERIALIZABLE. Then, the isolation property can be dropped and ACD (Atomic1 interpretation) would be the only properties of interest. There would be no inconsistent reads: Dirty Reads, Non-Repeatable Reads, and Phantom reads. This would obviously make the world a little bit simpler for us programmers. I will probably write about the feasibility of not relaxing the isolation property of transactions in a later blog post.

The database I am working on, BergDB, only supports the strongest isolation level: SERIALIZABLE. Actually, the only way to change the state of the database is through strong transactions. With optimistic concurrency control (STM), there is little to gain by introducing the read issues that can occur due to lack of isolation between transactions (Dirty Reads, Non-Repeatable Reads, and Phantom reads).

ACD transaction

Let us consider the original proposal by Gray with three essential properties of a transaction: atomicity, consistency, durability. Let us further consider a database with a global state that evolves over time from one state to the next by executing a transaction. Such transactions are easy to define in a precise way. Below, a transaction, f, is defined as a mathematical function that takes the database from one state to the next.

The first "property", atomicity, is part of the definition of the database and transactions. It implies that a reader can only read the distinct database states S0, S1, ... There is no visible state between those states. The other two properties are independent. We may have a transaction that is not consistent or one that is not durable. However, according the definition, it would not be a "transaction" then.

The above definition of durability is intentionally vague. It is an important concept worthy its own discussion. There is no such thing as a 100 per cent durability guarantee. Data could always be lost. Instead, the probability that a transaction result can be read in the future is a more accurate (but more complicated) model.

Conclusion

In my opinion, the original definitions of the ACID properties of database transactions are not well defined and confusing. There are multiple interpretations, and there seems to be no precise mathematical definition of them (please tell me, if you know one). I would prefer to work with the original three properties proposed by Gray: atomicity, consistency and durability. This set of properties can easily be defined in a precise way. An attempt to do so was made in this article.

References

[Gray1]  The Transaction Concept, Jim Gray, 1981.

[Gray2] A Critique of ANSI SQL Isolation Levels, Berenson, Bernstein, Gray et al, 1995.

[Haerder] Principles of Transaction-Oriented Database Recovery, Haerder and Reuter, 1983.

MathML: A Test

This blog post is to test how well MathLM works with browsers and with Blogger

This expression: ${\displaystyle {\int }_{-1}^1\sqrt{1-x^2}dx=\frac{\pi }{2}}$ is pretty cool to have inline.

${\displaystyle S_{i+1}=t_i\left(S_i\right)}$

The MathML code was generated with the editor at

http://www1.chapman.edu/~jipsen/mathml/asciimatheditor/

Java: Check your memory access time

Waiting for data is likely the most common thing your CPU is up to. Even when you CPU is running at 100%, it is likely to waiting for data from RAM. Random access to RAM memory is often a bottleneck in a "CPU-bound" Java program. Such programs should really be called RAM-bound, since their performance is bound by the performance of the RAM, not the CPU.

Out of curiosity, let's measure the performance of memory access from Java. We limit the test to summing values of a single long[] array. The memory size of the array is 0.8 MB when testing the cache and 400 MB for testing the RAM. The array is accesses either sequentially or using random access. So, we have a total of four test cases: cache with sequential access, cache with random access, RAM with sequential access, and RAM with random access.

My setup: an i7-3687U CPU (2.10 GHz), Ubuntu 12.04 64-bit, 4 MiB cache, Oracle JVM 1.7.0_25 (64-Bit, build 23.25-b01). The "-server" flag is used when running Java. Computer: Toshiba Portege Z930-14L.

My Java code. Consider it public domain, do whatever you like with it. It's all in one class and it has no dependencies besides a JVM. There are deficiences, of course. Code style has sometime been sacrificed for performance. Loop unrolling did not improve performance, however. There are many other things that happens then just accessing memory. Computation of the next index is a significant part of the cacheRan test.

    Test        Access time
    cacheSeq     0.33 ns,  0.69 cycles
    cacheRan     3.16 ns,  6.64 cycles
    ramSeq       0.56 ns,  1.37 cycles
    ramRan      20.07 ns, 42.16 cycles

Sequential access to the long[] array is surprisingly fast. It is interesting to note that accessing data from the cache in sequence results in less than a cycle per access. I believe this could be because SSE instructions are used. I have not confirmed this. It could also be because of Intel's turbo boost technology. The cycle time assumed is based on a frequency of 2.10 GHz.

Sequential access in RAM is on par with the result for sequential access to cached data. Random access to the cache is significantly slower (3 ns) and random access to the big RAM memory is many times slower (20 ns).

Cache-aware algorithms are important. More on that later.

Check the memory access time on your computer! Just run the Java class provided. Add the result as a comment, please.

UPDATE: Needless to say (?). It is very seldom a programmer would ever need to consider making his code cache-aware. Other things (disk/network IO) usually limits application performance. And the value of the product is seldom limited by its CPU performance anyway. Cache-aware algorithms are however interesting for me while creating BergDB. I aim at very high performance for data that fits into RAM - it should be on par with databases that assumes all data fits into RAM. It is also interesting for those who writes code for basic data structures: maps, set, lists and so on.

Welcome!

Welcome to my blog! I am Frans Lundberg, a curious software engineer and physicist who have spent quite some time on developing algorithms and software for the BergDB database. In this blog, I will share some thoughts and facts on databases and data storage in general. Everything from theory to measurements of disk performance is of interest.

I enjoy scientific papers on the subject and aim to keep a scientific approach. If there are experiments (performance tests, for example), I intend to make sure they are possible to repeat. Facts, knowledge, figures should have references. Tell me if I slip. This blog is hopefully useful for others, but it is also written for myself as a way of storing thoughts, results and useful references for future use.

Don't expect a post per day, or per week. I prefer quality over quantity and hope I can avoid polluting the Internet with even more garbage. Use your RSS reader to get updated when new posts are published.

Thoughts and opinions will be included in the blog, but I am not writing to preach or convince the reader of anything in particular. I am just a curious learner who wants to learn more about data storage. Hopefully, I can learn more together with you, my dear reader.