Misframe

Aug 5, 2018

Terrace Time Series Storage Experiment

I’m working on time series storage again!

My last “serious” time series storage project was Catena that I blogged about here. I wrote Catena to store time series data for a monitoring project I had, and the only use case I had was plotting charts. Since then my requirements have changed. My time series have to be more than arrays of points with simple string names. They have to be computed from events with lots of attributes that I can filter, group, aggregate, and rank.

What are events? They’re basically maps with timestamps, like the following log message:

{
  "latency": 0.438107,
  "level": "info",
  "method": "GET",
  "msg": "[Req 9090d339] status code 200, latency 0.44 ms",
  "request_id": "9090d339",
  "status": 200,
  "time": "2018-08-03T00:27:36Z",
  "url": "/goals/ZxbWA79Q"
}

And an example (pseudocode) query I could write against events like that is the following, which should return time series points representing the 95th percentile latency for HTTP 200 requests in 1 hour intervals.

SELECT QUANTILE(`latency`, 0.95) WHERE `status` = 200 POINT SIZE 1h;

Here are some more requirements:

The Terrace Experiment

This new project is called Terrace and it’s an immutable storage format for events. Other immutable storage formats are Parquet, ORC, and my own Catena’s on-disk partition format. The name comes from how I imagine the storage format being implemented, with lots of layers. Besides addressing the requirements I listed above, I want to implement automatic indexing. That’s going to be the most interesting part about this project, but I’m not sure if it’s going to be worth it. That’s why I’m considering this to be an experiment. I’m excited about this since I don’t think anyone else doing something like this, and it’s a combination of my favorite things: databases, time series, and machine learning.

Automatic Indexing

When you work with a relational database, you think about your data model, define your schema and indexes, and load your data. At query time, the database engine will consider statistics about your data and information about available indexes to generate an execution plan. The execution plan is limited to the indexes you’ve defined ahead of time. For this new project, I want to flip that around. Because I’m working with immutable data, I can let an algorithm analyze the data and determine how to structure and index the data for me.

What I mean by automatic indexing is building up index structures with column ordering and split points optimizied for certain queries on a data set.

                  Queries                          Data
 __________________________________________     __________
| SELECT COUNT(*);                         |   |    {}    |     ___________
| SELECT MAX(latency) WHERE user = 2;      |   |    {}    |    | Optimized |
| SELECT user, COUNT(login_time) AS logins | + |    {}    | => | Terrace   |
|   GROUP BY user                          |   | Raw data |    | File      |
|   ORDER BY logins                        |   |    {}    |     ^^^^^^^^^^^
|   DESC LIMIT 10;                         |   |    {}    |
 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^     ^^^^^^^^^^

How will this be done? Machine learning, of course :).

Most of my time with this project will be spent working on automatic indexing and determining whether or not it’s worth it to spend a large amount of compute resources to optimize the storage and access of immutable event data. Who knows, maybe brute force is actually more efficient.

Storage format only

For the past few years I’ve been focusing a lot on time series storage infrastructure. Infrastructure is not the problem. We’ve basically figured that one out. What we haven’t really figured out is how to build a truly cloud-native time series storage system. Cloud-native means separation of storage and compute, and I think we haven’t spent enough time on improving storage independent of compute. To focus on just that I’m going to work only on the storage format. This also narrows the scope of the problem to something I can work on myself. Others can figure out infra; it’s where things are really opinionated anyway.

Next steps

So far I have an idea and have done lots of research. The next steps are to start iterating on the storage format and work on analyzing data for automatic indexing. I also need test data, so I’ll probably have to write a test data generator. I’ll share my progress on Twitter and more posts.

Next read these:
Nov 23, 2023
Jan 11, 2023
Apr 9, 2016