Implementing a non-relational database in Go

In a previous Damn Cool Algorithms post, I discussed log structured storage, and how it applies to databases. For a long time, I've wanted to implement a database based on log structured storage, and a few other nice mechanics from other database systems:

  • Tables are key:value mappings, with duplicate keys allowed (Bigtable, BDB)
  • Map-based views, also known as materialized views, for indexing (couchdb).
  • Reducer support for views (couchdb).

Since my previous posts about go have been generally well received, and because I want to explore the language a bit more, I'll be implementing all this in Go. The approach I'd like to take is one of gradually building up abstractions. We'll tackle each of the components in its own post:

  1. An interface for writing records to an append-only file or set of files.
  2. A B-Tree implementation, built on the record interface.
  3. Map-based / materialized views, based on the B-Tree implementation.
  4. Reducers for views.

Unlike previous series, this one is likely to be fairly fragmented. There's a fair chunk of functionality to be implemented here, so I won't be able to get it out at my usual three posts a week schedule. In the meantime, the usual posts on App Engine and other topics will continue.

In the first post in the series, we'll implement an interface for writing records to an append-only file (or set of files), and reading records back, given their address. This may not sound like the most thrilling component, but it's necessary in order to implement the rest of the system, and we'll learn a lot about Go's IO interface by doing it.


blog comments powered by Disqus