Rock & Roll

RocksDB is a persistent key-value store, where Keys and Values are arbitrary byte arrays. It's maintained by the Facebook Database Engineering Team and built as a c++ library. The Story of RocksDB provides some background info and a wiki is provided in the repo.

Our goal right now is to make a simple hello world with RocksDB that will serve as the start of the info store.

1. Why RocksDB?

  • i like it
  • file system, storage medium, and mostly platform agnostic
  • Direct-IO
  • caters to a variety of use cases
the_rock.jpg
Figure 1: the rock

moving on.

2. Exploring Rocks

first step is to clone the repo and take a peak at the examples.

  • clone repo & compile static_lib
git clone https://github.com/facebook/rocksdb && cd rocksdb
make static_lib
cd examples/; make all

the examples don't output anything to stdout when they're run, but many of them store database files under a directory in /tmp which can be inspected. after compiling the library in the root you get a make_config.mk which is include'd in examples/makefile. worth checking out to get a better understanding of how examples are compiled (with g++).

let's take a look at the output of options_file_example:

cd ./media/01/rocksdb_options_file_example && ls
000012.log
CURRENT
IDENTITY
LOCK
LOG
LOG.old.1621383828949925
MANIFEST-000011
OPTIONS-000009
OPTIONS-000014

The LOG file looks like this:

 7f1c37455ac0 RocksDB version: 6.20.0
 7f1c37455ac0 Git sha a0e0feca6281e6f3c207757a15f6b99d3a67070d
 7f1c37455ac0 Compile date 2021-04-28 12:52:53
 7f1c37455ac0 DB SUMMARY
 7f1c37455ac0 DB Session ID:  73HSPOGLJMAK0WD2FX8D
 7f1c37455ac0 CURRENT file:  CURRENT
 7f1c37455ac0 IDENTITY file:  IDENTITY
 7f1c37455ac0 MANIFEST file:  MANIFEST-000004 size: 110 Bytes
 7f1c37455ac0 SST files in /tmp/rocksdb_options_file_example dir, Total Num: 0, files: 
# ...

and the OPTIONS file like this:

[Version]
  rocksdb_version=6.20.0
  options_file_version=1.1

[DBOptions]
# ...

DB Option Files are stored in INI format. There are a looooot of options and a lot of information shown in the LOG. Yikes!

3. Some Code

After poking around in the wiki for a bit and learning about the Basic Operations, we can build a helloworld-db tool of our own for testing. We'll also make a simple Makefile that compiles our code with Clang. We're not going to do much with this program right now since the examples and wiki provide plenty of reading material.

  • helloworld.cc

    boneless simple_example.cc from the examples

    #include <iostream>
    #include <string>
    #include <vector>
    
    #include "rocksdb/db.h"
    #include "rocksdb/options.h"
    
    using namespace rocksdb;
    
    std::string db_path = "infodb";
    DB* db;
    Options options;
    
    void run() {
            options.IncreaseParallelism();
            options.OptimizeLevelStyleCompaction();
            options.create_if_missing = true;               
            Status s = DB::Open(options, db_path, &db);
            assert(s.ok());
    
            std::string value;      
      s = db->Get(ReadOptions(), "some_key", &value);
      assert(s.IsNotFound());
    }
    
    int main() {
            run();
    
            delete db;
            return 0;
    }
    
    • Makefile

      compile helloworld.cc with Clang, link rocksdb dynamically (for now). We can see the linked .so files with ldd ./helloworld command after compiling.

      .PHONY: clean
      _: compile
      compile: helloworld.cc
              clang++ -Wall helloworld.cc -ohelloworld -lrocksdb
      
      clean:
              rm -rf helloworld
      

    After compiling with make and running ./helloworld we get some files dumped to ./infodb with the same structure as the examples.

4. Column Families

Column Families are a feature of RocksDB that allows us to logically partition our database. HOWEVER, these are not 'columns' as they are known in relational databases. Column Families are simply a new namespace for key:val pairs. If we implement our Column Families correctly , we can build a full database model, relational or otherwise. These features are what makes embedded key:val stores like RocksDB unique - they are primitive, and allow developers an insane level of flexibility in their implementations.

Going forward, how we partition our database through Column Families will play an important role in how useful it is, and how easily we can build additional layers of processing and API on top of it.

For now, we'll just take a peek at IndraDB and how Column Families are used in their implementation to store Graph data structures.

4.1. IndraDB Implementation

IndraDB is a Graph Database library written in Rust. It's heavily inspired by TAO (an excellent read btw) and allows for arbitrary Properties to be stored with any Node or Edge. IndraDB supports quite a few different backends, but we're only interested in the RocksDB impl, more specifically, lib/src/rdb. The column family names can be found in datastore.rs:

const CF_NAMES: [&str; 6] = [
    "vertices:v1",
    "edges:v1",
    "edge_ranges:v1",
    "reversed_edge_ranges:v1",
    "vertex_properties:v1",
    "edge_properties:v1",
];

vertices, edges, edge_ranges, and reversed_edge_ranges are directly derived from the TAO Model. vertex_properties and edge_properties represent encoded JSON objects (i.e. properties) that can be attached to vertices and edges. The first four Column Families are all we need to create the TAO Graph implementation so we'll focus on those and set aside properties.

Vertices are ("vertex_id" : "vertex_type") and Edges are ("edge_id" : "edge_type"), but what are 'edge_ranges' and 'reversed_edge_ranges'? The answer is evident when we consider what we actually get from vertices and edges. We get a single k/v pair, but no way to connect them, which makes them pretty useless by themselves. edge_ranges can be thought of as associations between vertices, indexed by time of insertion. It boils down to a k/v pair, but the key is a struct that looks like this:

pub struct EdgeKey {
    /// The id of the outbound vertex.
    pub outbound_id: Uuid,

    /// The type of the edge.
    pub t: Type,

    /// The id of the inbound vertex.
    pub inbound_id: Uuid,
}

and the value is a timestamp, resulting in a single Edge pair being:

pub struct Edge {
    /// The key to the edge.
    pub key: EdgeKey,

    /// When the edge was created.
    pub created_datetime: DateTime<Utc>,
}

These Edges (or associations) can be found in both the edge_ranges and reversed_edge_ranges column families, with the reversed associations being derived from the same EdgeKey struct but with the outbound and inbound ids swapped. This allows us to create bidirectional edges (as well as support parts of the TAO model, but not worth getting into here).