Implementing a non-relational database in Go
Posted by Nick Johnson | Filed under go, godb, coding, tech
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:
- An interface for writing records to an append-only file or set of files.
- A B-Tree implementation, built on the record interface.
- Map-based / materialized views, based on the B-Tree implementation.
- 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 ...