TrailDB

TrailDB is an easy portable C library that allows you to query a series of relative events. It is used to group the existing relative events in a time-series format and produce an immutable database with high compression rate.

It is designed as a complement to current existing relational databases or key-value stores and targeted for OLAP workload such as analyzing usage patterns, predicting user behavior, and detecting anomalies. One key design feature is that the database is immutable once produced. This immutability feature allows the TrailDB to reach another key feature - data compression. It leverages relativity among time-series events to achieve high compression. These two key features allow TrailDB to achieve good performance in OLAP workload.

History

TrailDB system has been developed by developers in AdRoll to handle the user-level analytics. The developers at AdRoll has seen the increasing number of requests for user-level analytics but found it hard to grasp and analyze a large user-level data using advanced SQL queries. Thus, they developed TrailDB system that is used to query a series of events at user-level.

TrailDB was first announced open-sourced on May 24, 2016. That version was TrailDB 0.5.

On May 15, 2017, version 0.6 was released. This version introduced the indexes and brought a new optimized query tool trck.

Isolation Levels

Serializable

When creating a database, there's only one process to handle it and others cannot access it. Once the database is produced, it is a read-only immutable file. Thus, everyone can issue read requests to it, but cannot issue any write operations. In this view, it is equivalent to the serializable isolation level.

Foreign Keys

Not Supported

In TrailDB, each database consists of a collection of trails each of which is identified by a unique UUID. There are no multiple tables within a database and no constraints among databases. Thus, it does not support foreign keys.

Compression

Delta Encoding Run-Length Encoding Prefix Compression

First, within a trail, events are always sorted by time. Thus, it utilizes Delta Encoding to compress the 64-bit timestamps.

Second, since events are grouped by UUID, which usually represents a logical entity such as an online shopping customer, these events within a trail tend to be predictable and TrailDB only encodes every change in behavior. This is not exactly the same as the Run-Length Encoding but similar.

Third, Huffman Coding, which is a kind of Prefix Compression method, is used to encode the skewed, low-entropy distributions of values.

Indexes

Inverted Index (Full Text)

This feature was introduced in TrailDB 0.6. It uses a specific inverted index to map each item to a list of page_ids. Each item is uniquely identified by a field and the value in that field.

TrailDB system provides the indexes by mapping each TrailDB item to a list of page_ids that contains that item. There is a file contains a HEADER and FIELD SECTION. TrailDB system looks into the HEADER first to get the filed's corresponding beginning offset of FIELD SECTION. Then, it finds out the corresponding item and extracts the page_ids containing that item.

Joins

Sort-Merge Join

TrailDB system offers the APIs to allow a multi-cursor merges multiple trails. As events within each trail are already sorted in timestamp order, TrailDB system leaverages this feature to perform a merge sort of multiple trails to produce a single merged trail.

Views

Not Supported

TrailDB system does not support views. But, as each database is an immutable file, users can create "views" by creating another immutable database by extracting data from the existing TrailDBs.

Storage Organization

Log-structured

It uses the log-structured storage organization.

Logging

Not Supported

TrailDB does not support logging and there's only one process to create the database. There is no recovery handler if the process crashes during the creation of the database. Thus, users need to start from the very beginning of the producing process.

But, TrailDB system allows merging existing TrailDBs to create a new immutable database. It is suggested to do so if there's a huge number of input events.

Concurrency Control

Not Supported

As each TrailDB is an immutable file, modifications are not allowed. There's only one process to produce a database and no one can issue read operations before the creation is finalized. Thus, there's no concurrency in TrailDB.

Data Model

Relational

TrailDB system adopts a specific relational data model. The traditional relational data model consists of a key and a set of different attributes. In TrailDB system, it consists of a key called UUID and a list of one complex type.

TrailDB system defines a thing called trail that is uniquely identified by a UUID. Within each trail, there is a list of ordered events, each of which is identified and ordered by the timestamp. For each event, it contains values for the pre-defined set of fields. These fields are the actual attributes in the traditional relational data model.

This data model allows the relative events belonging to one UUID, taking one online shopping user as an example, to group together in the order of time. Thus, it offers the predictability feature among the list of events and enables TrailDB system developers to use several compression methods to achieve high compression rate and extraction speed in TrailDB.

Checkpoints

Not Supported

TrailDB does not support checkpoints as each database is immutable once produced.

Query Execution

Vectorized Model

TrailDB system does not support the SQL query language. Instead, it provides custom API in the languages listed above. According to its source code, users should use get_trail function to reset the cursor to one trail and next function to consume the next event. It also offers a multiple-cursors version to emits a batch of events. This query execution is a vectorized model.

Storage Architecture

Disk-oriented

The database is an immutable file on the disk. TrailDB system has used the relativity among events to offer secret sauce compression on the data. It stores both the compressed data and metadata on the disk, the latter of which is used to explain the original data when needed.

Query Interface

Custom API

TrailDB system does not support the standard SQL query interface. It offers the query interface in several programming languages: C, Go, Python, R, Haskell, and D. TrailDB system also provides two specific languages to query the data. One is called trck, which is a domain specific language to aggregate metrics based on events of identical UUID. The other is called Reel, a small general query language for TrailDB.

System Architecture

Embedded

Stored Procedures

Not Supported

Each TrailDB is a read-only immutable file, it does not support stored procedures.

Query Compilation

Not Supported

TrailDB Logo
Website

http://traildb.io/

Source Code

https://github.com/traildb/traildb

Tech Docs

http://traildb.io/docs

Developer

AdRoll Inc.

Country of Origin

US

Start Year

2014

Project Type

Commercial, Open Source

Written in

C

Supported languages

C, D, Go, Haskell, Python, R

Licenses

MIT