NoSQL's CAP theorem busters: We don't drop ACID
'We are not relational fans here'
CAP theorem* holds no fear for six engineers building FoundationDB, the industry’s latest NoSQL candidate. The difference? It adheres to the principles of ACID** found in relational, which previous NoSQLers have tried to replace.
“A lot of people developing NoSQL systems have been discouraged by the CAP theorem and used that as an excuse for not solving some of the hard problems,” FoundationDB co-founder and MIT computer science graduate Dave Rosenthal told The Reg. Rosenthal started FoundationDB in 2009 with Nick Lavezzo and and Dave Scherer.
“It’s a heck of lot easier to build a database without transaction integrity than with it. If I was staring down the barrel of building a really big database I would use CAP theorem as an excuse not to do that,” he says.
Rosenthal’s team is mid-way though what he calls a “soft” alpha, with a beta due in early 2013. Early interest has been substantial, surging to the top of Hacker News during the summer. “We got a lot of questions and requests for the software. We’ve been scrambling to keep up with that.” Rosenthal told us.
Also, Rosenthal reckons, FoundationDB’s seeing search traffic on the start-up’s site reflect the fact people are looking for “ACID NoSQL” or “ACID key value store.”
“The issue for devs is pretty simple: NoSQL helps solve scaling problems, but throws another monkey on your back - writing code without the guarantees of transactions... If you can solve both problems, it's a real win,” he told us.
'We started reading the fine print on the [NoSQL] databases and none provide transactional integrity' - FoundationDB co-founder Dave Rosenthal
The problem comes back to CAP theorem, articulated by University of California Berkeley professor Eric Brewer, which states it’s impossible for distributed computer system to simultaneously achieve consistency for data on all nodes, to provide availability of either data or a request regardless of a failure in the system, and partition tolerance – the ability to continue working should a part of the system break down.
It’s the consistency part that puts the “C” in ACID – atomicity, consistency, isolation and durability. ACID is is a fundamental principle of relational databases that has helped make them a multi-billion-dollar mainstay of computing.
CAP theorem clearly poses a theoretical problem for cloud computing, where services are being founded on massively distributed servers for their compute and storage.
Hence, we’ve seen a proliferation of NoSQL for use in large, distributed data centres that have jettisoned ACID to achieve scale - column store Cassandra from Facebook and Google’s BigTable, document stores MongoDB, and CouchDB.
But recently there’s been a dawning recognition among NoSQL practitioners and those working in Big Data that the fast-iterating data they process needs to be demonstrably reliable, too. The result has been NoSQL databases adding more relational functionality to their software.
Indicative of the growing interest is Spanner from Google, the poster child of web-scale and distribute computing that helped popularise Big Data with MapReduce. Spanner is Google technology that can dictate where data is stored in a distributed cluster - and then time-stamps it so an application knows which version is current.
FoundationDB is Rosenthal’s second tech venture – he was employee-number-one at web-analytics company Visual Sciences that was sold for $60m to WebSideStory. It’s now part of Adobe's online marketing and web analytics unit Omniture.
Rosenthal said he believes FoundationDB is the next generation of the database market. He says he decided to apply himself, and hire a team, dedicated to solving an obvious problem.
Read the fine print
“Several years ago we looked at the market – the NoSQL database market,” he says. “The attributes are attractive - we are not relational fans here, we are more software engineers than DBAs, so that resonated with us. Also the price, and scale, to deploy on the cloud resonated with us.
“But then we started reading the fine print on the databases and none provide transactional integrity.
"Of course we read about the CAP theorem like everybody else did. But what the CAP theorem says isn’t as strong as what some people make it out to be... CAP theorem sounded scary and scared people building NoSQL databases off doing ACID transactions. So we said: ‘What if we throw out all the features and just try to make a fundamental data structure like a key-value store that’s scalable and has true ACID transactions?'."
“We all come from a theoretical comp sci background - not the traditional start-up hack-it-together mindset. We have an East Coast computer scientists' mindset and we realised what the world needed was just not another website; the world needed a solution to solve this problem. We feel too much of smart people’s time is spent trying to half-solve this problem in their own databases, database centres and their companies. We looked at the problem and decided it can be solved.”
So what is Rosenthal and his team proposing?