Misframe

Jul 3, 2015

Solving Time Series Storage with Brute Force

Many months ago, I first read “Searching 20 GB/sec: Systems Engineering Before Algorithms” [1], an excellent post by Steve at Scalyr. I re-read it six months ago when I was on winter break between semesters of college. I was traveling, working on Cistern [2], and thinking about time series storage.

By “thinking,” I mean “annoyed.” I was using Bolt [3] (the B+tree-based, transactional storage engine implemented in Go) to store Cistern’s time series. The implementation I had was pretty inefficient. There was one key-value pair per time series point without any compression. There was a significant amount of overhead with this approach, especially considering my time series points were 12-bytes at most (8-byte timestamp plus 4-byte float value). I could have implemented compression by packing multiple points into a single value, and then compressing afterwards, but then I’d have to implement batching and all of the compression logic myself.

At some point I just went, “forget B-trees, forget log-structured merge, forget everything!” and decided to try to brute force it. I just need to store a bunch of arrays. How hard could that be, right?

Fast forwarding to the present, you may have seen my blog post introducing Catena [4], heard me talk about it at a meetup or watched a webinar [5], or heard about it from some other source. There are so many topics that get covered when I talk about Catena, and you may think that it took a lot of researching time to come up with its design. That’s isn’t the case. The truth is that it has mainly been brute forced! Problems and challenges came up as I was implementing it, and they needed to be solved.

The really interesting thing now is that the current design is not unique at all. In fact, it could probably be replicated with RocksDB. How about that? I started from scratch and now it seems like the path leads to RocksDB.

I’d like to remind you that I didn’t want to write a time series storage engine. I guess it’s what I’m mostly known for now, but that was a complete accident. I never expected this to actually work.

But it does. Cistern no longer uses Bolt and has been using Catena for a while. I now have time series storage with compression, and it works well enough for me to build a dashboard that I can use to monitor my systems.

I guess the moral of the story is that brute force can yield some interesting results. You may end up finding a solution to a problem, like I did when I finally got a better time series storage engine for Cistern. Or, more importantly, you may find that it leads you in a direction that may not have been so obvious when you started off. So, what are the next steps? I’ve already solved my own time series storage problem, but if I had something that needed to be “production ready,” I’d start looking at RocksDB.


[1] Searching 20 GB/sec: Systems Engineering Before Algorithms
[2] Cistern
[3] Bolt
[4] State of the State Part III
[5] Catena: A High-Performance Time Series Storage Engine

Next read these:
Mar 5, 2015