Readings in Databases
rxin.github.io
rxin.github.io
Database Systems: The Complete Book by Garcia-Molina, Ullman, and Widom seems to be one of the few full books with decent coverage of implementing a database, even though anyone wanting to implement a modern database will have to go a long way from what it covers.
There are a ton of great papers out there easily accessible, though, at least in part thanks to the VLDB Endowment. The people at MS Research working on databases publish a lot of great papers, too.
I wanted a list of papers that would be essential in building database systems. It was little bit sad to see many members of the community re-discovering and re-inventing the wheels from 30+ years of relational database and systems research. This list of papers should help build a solid foundation.
I for one would be very interested in that, although perhaps the deprecation of spinning disks has reduced the complexity of the issue.
Discussion between Postgres & Linux devs: http://lwn.net/Articles/590214/ & https://news.ycombinator.com/item?id=7521008
SSDs are much more complicated than spinning disks, so if anything the problem has gotten worse.
All of these database systems have extremely different host requirements and write characteristics. Even SQLite and MySQL can be pretty different depending on the storage layer (SQLite can use BerkeleyDB)
The future isn't MySQL and spinning disks, the future is a tens of different databases that do things and handle reliability in a variety of ways. I know that complicates the issue even more, but my point would be that writing a halfway decent database is possible (or impossible, depending on your perspective) within a lot of this literature.
( Also, spinning disks even have abstractions since mostly you are using a RAID controller with a decent size of cache to alleviate random writes. )
What I meant with halfway decent database is one that can actually guarantee the data it committed is actually on the hard drive in a readable state, and that can sustain random writes at a rate close to the theoretical limit of the persistent storage device. I'm not judging any databases in particular. I'm asking how can I make a database that's as awesome as MySQL or Cassandra.
All these databases have already taught us a lot of what's in these articles, but one thing that isn't written about a lot is how they actually achieve high performance, not just in a theoretical way, but in a practical way. What system calls do they make, what schemes do they use to minimize seeks, how is the memory laid out. None of that high level "do we use Paxos of Raft", that's kids stuff.
Those papers have a lot of that information, but it's usually a bit buried.
> What system calls do they make
I think that's actually kind of out of scope for a paper, because already you are assuming an OS and a language. Many papers/articles assume neither.
> what schemes do they use to minimize seeks
Look for information on buffer management/buffer managers
> how is the memory laid out
Almost always in pages that correspond to disk blocks. Also it's dependent on lots of things (transactional model, index types, column vs row orientation, etc..) This is heavily tied into the buffer management stuff too.
This one is a classic as well: What Goes Around Comes Around (Michael Stonebraker, Joseph M. Hellerstein) – http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.113....
"This paper provides a summary of 35 years of data model proposals, grouped into 9 different eras. We discuss the proposals of each era, and show that there are only a few basic data modeling ideas, and most have been around a long time."
> Assuming you're right that this is a trend
Here is one list of lists, https://github.com/sindresorhus/awesome
For people who looked at this wanting to get going with using database systems (as opposed to creating them), I'd recommend:
Learning SQL by Alan Beaulieu
SQL Performance Explained by Markus Winand
SQL Cookbook by Anthony Molinaro
This sentence nailed what I thought was wrong with some early decisions in NoSQL systems: "because partitions are rare, there is little reason to forfeit C or A when the system is not partitioned."
If your system requires response times faster than that, the data centres you don't have time to contact behave sort of like they are partitioned all the time.
Me, I tolerate writes that take a bit longer to keep things simple :)
[1] http://www.nsmith.net/articles/2011-08/latency-between-amazo...
It's not just to keep things simple, it's to keep things consistent :-) Some NoSQL systems (e.g., MongoDB) introduced a new P in the equation (Performance) and used this to justify a lot of questionable decisions that affected consistency (and durability!). They have come a long way since these early decisions though.
If a system considers moderate latency as a partition, it would need to perform partition recovery on every write. That's why I'm not sure considering latency as partition is in line with the CAP theorem.
Maybe it is more related to availability though (not sure).
edit: I guess this is written from a very web-tech point of view, where the assumption is often made that reads will dominate writes. Obviously that's not always the case, and the tradeoffs get a lot more complicated!
By separating the behavior under failure (Consistency or Availability) and the behavior without failures (Consistency or Latency), PACELC clearly communicates that these are different tradeoffs.
No idea if legal...
Link : http://www.extension.harvard.edu/courses/database-systems
[1] http://mitpress.mit.edu/books/chapters/0262693143chapm2.pdf