Overview

Thursday, 25th August 2022

Now that I’ve started a blog/journal/stream of consciousness on my site I figured that the CeresDB project I put together might make for a good first topic. To start with, I want to talk about the motivation behind it.

Back when I was a research assistant at the Cline Center for Advanced Social Research, MongoDB was a part of the data processing pipeline I worked on. To be clear, this wasn’t my decision, but instead a requirement of the PETRARCH2 which the pipeline was built around.

I have to say, my experience with MongoDB wasn’t great. Its performance was horrible, it was a pain to query, and it constantly crashed (I will admit this could be to misconfiguration on my part, I wasn’t exactly an experience MongoDB admin so I didn’t quite know what I was doing). Now that was years ago, so maybe it’s gotten better, but my next experience with it wasn’t great either.

At my next gig we used MongoDB for a variety of projects. Specifically, we used it to store arbitrary JSON records which sounds like a great fit for MongoDB, however it left a lot to be desired. The lack of schema (at least in how we were using it) meant that it was difficult to know what to add when creating a new object (which is partly due to the implementation, not MongoDB’s fault entirely). In addition, the tendency to nest objects within MongoDB records meant that navigating the information returned programmatically was a pain.

Anyway, while MongoDB very well could have been a great choice for this situation, it definitely left a bad taste in my mouth which led me to want to use a different database solution for my model operations solution, VelociModel.

I’ll admit, I don’t have much experience with many different database systems. Mainly it comes down to being a user of SOLR and interacting with MongoDB and PostgreSQL in a professional setting. SOLR didn’t impress me when I used it, so I didn’t consider that, so PostgreSQL it was. However, PostgreSQL has one important limitation, it doesn’t support nested objects. For the most part this wasn’t necessary for what I wanted to do, however I did need that functionality for storing metadata.

Yes, there are ways I could have achieved this with Postgres, however I thought this was the perfect excuse to design my own database and subsequently learn about the challenges and limitations that go along with that

As for how I designed the database, I decided to store data on disk for simplicity and scalability in a structure that represented hwo the data was stored in the database, more on that in a bit. Specifically, a database (foo) would look like this with a table (bar) would look like this:

data
|--- foo
     |--- bar
          |--- <first file uuid>
          |--- <second file uuid>
          |--- <third file uuid>

Each of the files inside the table contains JSON lines which are each a record inserted into the database. These records can then be referenced using a id of <file uuid>.<line in the file which holds the record>. This allows for quick retrieval of records by ID. This then leads us to the index system.

Indices are again based off of a file hierarchy. Using the previous example, with a group of records with the value field set to hello and a group of records with the value field set to world, the structure would look like this:

indices
|--- foo
     |--- bar
          |--- value
               |--- hello
               |--- world

Each file under the corresponding field name is just a list of all IDs that correspond to that value. This makes selecting records by value extremely easy. For example, say we want to get all the records which have value set to hello, we just read the file at indices/foo/bar/value/hello and now we have the location within the database files where all the records we want live. This can then be extended to more complex queries by performing operations and comparisons on the list of IDs from various key files.

One problem does present itself with this approach, specifically complex data values take more work to break down into indices. The way to get around this however, is to create more indices depending on what the data type is.

CeresDB supports complex LIST and DICT datatypes, so those need to be handled as well as as the STRING datatype

The approaches to handle the “problematic” datatypes are broken down as follows:

These complex indices have not been implemented yet, but will be in a future update of CeresDB, so these approaches are subject to change

• STRING

  • To handle string searching, we want to be able to search for full strings as well as substrings. To accomplish this, we store the full string as an index and then on queries we grab all the file names within the key’s directory (essentially the full text of each string) and then we can search and perform string operations to determine which indices match.

• LIST

  • Lists get to be a bit more complicated because we need to know the datatype of its composite values in order to run comparisons against them. Thankfully, Go allows us to inspect and figure out those datatypes. We can then create index files for each value in the list and search on those. In addition, we can create a .length index directory containing index files of the various list lengths which will allow us to then search based on that property.

• DICT

  • Trying to index dictionaries is both complex, and relatively simple. In order to do this, we just need to create an index directory for each dictionary value, then have an index within the directory according to whatever datatype the value is.

At its core, CeresDB uses this data storage method, the indices, a cursor for reading/writing data (we won’t get into that in this post), and a query language in order to function.

There are higher order functions, like user management and permissions, that I might address in a future post

The query language was inspired by REST apis, specifically the usage of DELETE, GET, PATCH, POST, PUT for retrieval and modification of data. One language feature that I wanted to add in was the ability to pipe outputs between commands. For example, if I wanted to get records from a table and then filter them by some condition, instead of

SELECT * FROM <table> WHERE <condition>

I would use

GET <collection>.<table> * | FILTER <condition>

The reasoning for this is that I wanted to make the query language friendly for developers, specifically those who utilize the command line frequently, so the inclusion of a Bash-like pipe operator made the most sense to me.

There’s a lot more that makes up CeresDB, but those are the main components that I think make it stand out from other database solutions. Not to mention that it has decent performance for a custom-built database engine, able to filter ~2.5 million records per second with Postgres able to filter 5-10 million records per second.

I’ll probably post more later with in-depth looks at various aspects of the system, but for now thanks for reading!