DZone
Thanks for visiting DZone today,
Edit Profile
  • Manage Email Subscriptions
  • How to Post to DZone
  • Article Submission Guidelines
Sign Out View Profile
  • Post an Article
  • Manage My Drafts
Over 2 million developers have joined DZone.
Log In / Join
Refcards Trend Reports Events Over 2 million developers have joined DZone. Join Today! Thanks for visiting DZone today,
Edit Profile Manage Email Subscriptions Moderation Admin Console How to Post to DZone Article Submission Guidelines
View Profile
Sign Out
Refcards
Trend Reports
Events
Zones
Culture and Methodologies Agile Career Development Methodologies Team Management
Data Engineering AI/ML Big Data Data Databases IoT
Software Design and Architecture Cloud Architecture Containers Integration Microservices Performance Security
Coding Frameworks Java JavaScript Languages Tools
Testing, Deployment, and Maintenance Deployment DevOps and CI/CD Maintenance Monitoring and Observability Testing, Tools, and Frameworks
Culture and Methodologies
Agile Career Development Methodologies Team Management
Data Engineering
AI/ML Big Data Data Databases IoT
Software Design and Architecture
Cloud Architecture Containers Integration Microservices Performance Security
Coding
Frameworks Java JavaScript Languages Tools
Testing, Deployment, and Maintenance
Deployment DevOps and CI/CD Maintenance Monitoring and Observability Testing, Tools, and Frameworks
  1. DZone
  2. Data Engineering
  3. Databases
  4. Database Building 101: The Storage Layer

Database Building 101: The Storage Layer

Get into the nitty-gritty of how a database's storage layer works. Follow Ayende Rahien as he puts one together with Voron as part of his new series.

Oren Eini user avatar by
Oren Eini
·
Aug. 17, 16 · Tutorial
Like (1)
Save
Tweet
Share
2.71K Views

Join the DZone community and get the full member experience.

Join For Free

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.

Database

Published at DZone with permission of Oren Eini, DZone MVB. See the original article here.

Opinions expressed by DZone contributors are their own.

Popular on DZone

  • How To Generate Code Coverage Report Using JaCoCo-Maven Plugin
  • Memory Debugging: A Deep Level of Insight
  • Microservices Discovery With Eureka
  • 2023 Software Testing Trends: A Look Ahead at the Industry's Future

Comments

Partner Resources

X

ABOUT US

  • About DZone
  • Send feedback
  • Careers
  • Sitemap

ADVERTISE

  • Advertise with DZone

CONTRIBUTE ON DZONE

  • Article Submission Guidelines
  • Become a Contributor
  • Visit the Writers' Zone

LEGAL

  • Terms of Service
  • Privacy Policy

CONTACT US

  • 600 Park Offices Drive
  • Suite 300
  • Durham, NC 27709
  • support@dzone.com
  • +1 (919) 678-0300

Let's be friends: