A NoSQL Reading List

I've been putting together a list of papers for interns, post-docs, and other new folks at Almaden who are getting interested in the NoSQL/NewSQL space. Here's what I have so far. Any suggestions/additions to the list would be welcome -- leave them around as a comment.

Basic System Design
BigTable,  Dynamo, and PNUTS are the three big systems running real applications and should be required reading. FAWN is an excellent read. The HStore paper talks about traditional OLTP, but is definitely closely related. Hyder is also in the traditional OLTP space and is probably less relevant to the NoSQL space than HStore, but this is a very cool system and explores a major departure from traditional OLTP system design. The RamCloud effort from Stanford has made some interesting choices that allow very good availability numbers. Finally, I'll include a shameless plug for my own paper, Spinnaker, which I think makes some interesting points about this space.


Consistency, Indexing, Transactions

• PNUTS Indexing and Views 
• Google Megastore 
• Helland's CIDR 2007 paper, and the one in 2009 with Campbell. I've had so much fun reading these.
• Dave Lomet's take on transactions in the cloud 
• Abadi's musings on CAP and PACELC
• Hellerstein's group on quantifying eventual consistency
• PiQL , a project from Berkeley, makes some interesting arguments on guaranteeing bounded time querying: 

Other Industrial/Open-Source Systems and Articles

• Curt Monash's valiant struggle to distinguish between traditional OLTP and "NoSQL" apps: HVSP 
• Industrial MySQL Scaleout approaches: Clustrix, Schooner , dbShards
• Oracle NoSQL Whitepaper 
• HBase, Cassandra, MongoDB -- codebases/architecture

Spinnaker, Paxos, and Gaios

Here's a great paper from Bolosky and others at Microsoft that demonstrates that Paxos can indeed be used as a high-volume replication protocol. They argue that a Paxos-based storage service can provide performance close to what the underlying hardware can support. You don't have to resort to simple primary-backup schemes which make it difficult to deal with arbitrary machine restarts. Also, you don't have to give up sequential consistency for performance and deal with the complications of eventual consistency. The crux of their argument is: for a system that is in a single datacenter, and needs to use commodity networking and disks, the Paxos implementation will certainly not be the bottleneck.

They implemented this in the context of a storage system called Gaios. The paper has plenty of implementation details and performance results. They even ran an OLTP benchmark on SQL Server configured to use Gaios storage. Neat stuff!

Spinnaker exploits the same ideas as Gaios, but the exposes a user-programmable key-value store API instead of building scale-out storage. The results from Gaios independently verify the arguments we tried to make in the Spinnaker paper -- you can use a consensus algorithm for data replication in a scale-out system without sacrificing performance.