Justin Santa Barbara’s blog

Databases, Clouds and More

Day 3: Repaying Technical Debt

I’m building a set of open-source cloud data-stores in December, blogging all the way.

In our last episode, we took the basic design that we’d used on day 1 to build an AppendLog, and built a basic key-value store that could store values. I had to take lots of shortcuts to get so far in the first two days, and much of today was spent catching up on the technical debt, with a few new features.

First off, I created a shared project in maven, which means we don’t have to keep repeating the version of the libraries. You can do this in a parent module or in a shared project, but it makes everything a lot more DRY. I’d also copied-and-pasted some code, so I then moved that code into the shared project. A quick Kata to start the day!

We had tests, but we weren’t running them automatically. I set up CircleCI, which is a hosted continuous integration which I love because it is so fast (slow CI means you don’t get the rapid feedback loop which makes CI so useful). In order to do that, I set up Barge as a git submodule so it effectively becomes part of the project. Git submodules are great, but suffer from a truly terribly CLI interface. Technically we could have got away without doing this right away, because Barge is awesome and is deployed into the maven repositories, but we know that we’re going to want to make changes to the Barge code to add some features, so the git submodule is the way to go. A bit of messing around with some maven details, and the CircleCI build was up and running.

The tests are more integration tests than unit tests: they launch a cluster of servers (embedded in-process) and then test using the public HTTP interface. I find that integration tests are a lot more stable, so there’s less need to constantly fix the tests; I think they’re testing the right thing - our public contract. I also find that unit tests are much less important in a strongly typed language like Java than they are in a weakly-typed language like Ruby or Python. If you find yourself needing a lot of unit tests, you may not be using the compiler to maximum advantage: consider introducing some strongly typed classes to enforce what you’re testing. In short, you may be writing Old-Java, not New-Java. There are exceptions to the rule of course; unit-testing implementations of complicated algorithms is generally a good idea, for example!

Next up was enforcing uniqueness of keys, because although our generic BTree can support duplicate keys, we don’t really want duplicate keys in a key-value store. So now we can replace values, and we added a test to verify that.

Then, support for deletion by key. Previously the only change supported was insertion, so it was important to figure out a good approach here. Rather than have a set of methods, one for each action, instead we have a doAction method, which is parameterized with an Action enum. We have to do this for the Raft log anyway: every action must be serialized as a message, the idea is simply to use that message, rather than fight it and marshall/demarshall back and forth and switch before dispatching to a set of similar methods.

Finally, I cleaned up the transaction handling, following the basic design of LMDB. For each transaction commit, we write the new root page id into a section of the file header, rotating through a fixed-array of slots. When we start up, we scan the section, looking at these slots to find the newest root. This is how read transactions can run without locking (at the expense of write transactions needing to do copy-on-write). I extended the LMDB approach a little bit, by writing a special “transaction record” page for each write transaction, which includes the root page id, a transaction sequence number, and a pointer to the previous transaction. The slot in the header includes a pointer to that transaction page, as well as the root page id (which is redundant, but avoids having to fetch the transaction page to find the root page id). I’m thinking this will help when it comes to implementing page-reclamation (garbage collection), and that it may be more useful generally: we’ll see!