Database Building 101: The Storage Layer

We are going to be using Voron to actually handle the storage of the data. Voron is a low-level storage engine, which provides, among other things, full ACID compliance, MVCC, and high performance.

For today, what'll look at are the following operations:

• Add a node.
• Add an edge between two nodes.
• Traverse from a node to all its edges (cheaply)
• Traverse from an edge to the other node (cheaply).

Here is the interface code that we will need to build:

public class GraphDatabase
{
    long AddNode(NameValueCollection node);
    long AddEdge(string type, long from, long to, NameValueCollection edge = null);   
    NameValueCollection GetNode(long id);
    IEnumerable<Tuple<long, NameValueCollection>> GetEdgesFor(string type, long id);
}

I tried to make it as simple as possible. I’m using NameValueCollection because it is a trivial property bag to serialize/deserialize without bringing any additional dependencies.

Let's focus on the initialization of this class. We need to create a StorageEnvironment in Voron, and set up some structures.

public class GraphDatabase
{
    private TableSchema _emptySchema = new TableSchema
    {
        AllowNoIndexesOrPrimaryKey = true
    };
  
    public GraphDatabase(StorageEnvironmentOptions options)
    {
        _env = new StorageEnvironment(options);
    
        using(var tx = _env.WriteTransaction())
        {
            _emptySchema.Create("Nodes", tx);
            _emptySchema.Create("EdgesData", tx);
            tx.Commit();
        }
    }
}

Voron has several different storage options for data, and in this case, we are using a table. A table (which is very much unlike an RDMBS table) is a way to store records that have some indexes, but in this case, we are doing something strange. We are defining a table that has no indexes (this is so strange that we need to explicitly allow it). This is useful because tables manage indexes for us automatically, but in this case, we will use them strictly for storage. We’ll see why in just a bit.

public unsafe long AddNode(NameValueCollection node);
{
    using(var tx = _env.WriteTransaction()
    {
        var nodesTable = new Table(_emptySchema, "Nodes", tx);
        string serializedNode = SerializeNode(node);
        byte[] data = Encoding.UTF8.GetBytes(serializedNode);
        fixed(byte* pData = data)
        {
            long id = nodesTable.Insert(new TableValueBuilder
            {
                {pData, data.Length}
            });
      
            tx.Commit();
            return id;
        }
    }

The code here is a bit strange. Tables are actually meant to hold multiple values and define indexes based on this. So using them to store a single value is something that you wouldn’t normally do. Except that the ID that we get back from the table has a very interesting property. It has O(1) cost of access. So given a node ID, I can access it directly, regardless of how big my database is. That is a property that I want because, effectively, random access of nodes is something that happens quite a lot and is highly desirable.

Now, let's see how we can connect two edges, shall we? This code ignores all error handling, missing nodes, etc. It is meant to explain the core stuff, this is a toy database, after all.

public unsafe long AddEdge(string type, long from, long to, NameValueCollection edge = null)
{
    using(var tx = _env.WriteTransaction())
    {
        long edgeId = -1;
        if(edge != null)
        {
            var edgesDataTable = new Table(_emptySchema, "EdgesData", tx);
  
            string serializededge = SerializeNode(edge);
            byte[] data = Encoding.UTF8.GetBytes(serializededge);
            fixed(byte* pData = data)
            {
                edgeId = edgesDataTable.Insert(new TableValueBuilder
                {
                    {pData, data.Length}
                });
            }
        }
        var edgeTypeTree = tx.CreateTree("Edges_"+ type);
        var fixedSizeTree = edgeTypeTree.FixedTreeFor(from, valSize: 8);
        fixedSizeTree.Add(from, Slice.From(tx.Allocator, (byte*)&to, sizeof(long));

        tx.Commit();
    }
}

Here we continue doing strange stuff. We already know that we use the empty schema table to have an O(1) access to data. And we store the edge’s data there. But then we run into some new stuff. We create a B+Tree called “Edges_”+type, which hold all of the edges of a particular type. But the content of this B+Tree is not simple. Instead, it is using fixed-size trees. Those are also B+Trees, but they have well-known sizes both for keys (which must be long) and the value (which must be small, fewer than 256 bytes). Because they are very compact, we can pack quite a lot of data into them and work with them efficiently.

The end result is that we are now storing the node data and access it at O(1) cost. We also store a B+Tree full of fixed size tree (whose name is the source node id) and whose keys are the destination nodes, and the values are the edge data.

Confusing yet? Not much different than Dictionary<SourceNodeId, Dictionary<DestinationNodeId, EdgeDataId>>. That is quite enough for today. Next, I’ll show how we can traverse the data, and what kind of costs are associated with it.