SurrealDB’s Sophisticated Storage Solution — SurrealDB Internals Part 4

Photo by Calvin Hanson on Unsplash

Hot tip: All stories in this series are here

There is an old programming saying that it is usually better to have simple code that is easily explainable than obscure code that is more performant. This is definitely one of the exceptions.

The only way I know how to describe the way Surreal stores it’s data is as brilliant, simply brilliant.

In order to understand how the data is saved, let’s first look at what needs to be in storage. There are two categories of items to store:

1. Metadata — the structure of tables, indices, scopes, etc.
2. Data — the values of the objects retained by Surreal

As the underlying storage is a key-value store, both are stored in a similar way, but the values stored for each are different.
In order to better demonstrate how Surreal stores data, I built a small application to read the RocksDB file that Surreal stores it’s data in (if the server is started with a file path).

Running the RocksDB Viewer

First, we start both the server and SQL prompt:

surreal start rocksdb://local.db --user root --pass root
surreal sql --conn http://0.0.0.0:8000 --user root --pass root --ns test --db test

Second, we insert some data:

-- create new tables and records
CREATE user:oricc SET name="Ori";
CREATE user:tobie SET name="Tobie";
CREATE repo:surrealdb SET name="SurrealDB";

-- Add some relations
RELATE user:tobie->contributes->repo:surrealdb;
RELATE user:ori->contributes->repo:surrealdb;

then, when we run the app, we get the following results (the left column is the key, the right is the value):

Let’s break down what we see, starting with the metadata.

The first rows describe the objects in the database:

Surreal has several types of objects, here we can see the namespace, database, and tables that are defined in this server.

Now the question becomes what the keys and values represent. In order to understand that, we’ll go back to the code.

Understanding Keys

Surreal has an entire directory (lib/src/key) which deals with creating the keys for the various different objects. For this example, we’ll look at our old friend, the table.

The struct defining the table key has the following structure:

At first, this struct looks very odd. What are all those variables with the unconventional names? what are we representing here? Look closer, does it look familiar? Let me give you another hint.

When creating the key it’s values are initiated as follows:

Yes! This struct is directly mapped to the key for the tables that we can see in the image above!

How the struct is turned into the key is another interesting point. Notice in the struct definition, the struct macro-derives the Key macro, which automatically creates the serialization and deserialization methods for the struct using the msgpack format. MessagePack is a protocol for efficiently compressing data into a minimalist format, Surreal uses the serde binding for the protocol (rmp_serde) so that structs can be easily mapped to and from the serialized data. For those interested in the macro itself, you can have a look at the code.

Understanding Values

The second element of the metadata is the values.

In order to understand what the value of the metadata stores we need to look back to the previous post and review the table definition statement:

Now compare the struct to the value for the “contributes” table:

��contributes�����None�None�None�None

This is an exact map of the table definition, again using the Store macro to create the MessagePack methods on the struct that translate it to the value we see in the RocksDB.

What this allows us to do is to always have the entire definition for each of the objects in the database, and act accordingly.

Item storage

For any non-metadata items we need to save in the key-value store, we can easily see that they are very similar to the metadata:

Each item is stored with the entire hierarchy (Namespace -> Database -> table -> ID) and the value is the MessagePacked object itself (notice the name and Ori inside the value).

That’s it for storing the values themselves.

The next question is why the keys have this format.

Breaking down the key structure

The structure of the keys is actually the reason this storage design is so brilliant. In order to understand why, we first need to understand how access to key-value databases is done. There are two methods of accessing a KV store.

1. Key-based — we look up a specific key and get the value for it
2. Scan — we look up a range of keys and retrieve all the values.

By design, key-based lookups are extremely efficient, while scans are a little slower. For that reason, we want to have the range we are scanning be as small as possible.

The way Surreal achieves this is by building the keys in a hierarchy that allows us to translate each key type into a key range in the underlying KV storage.

Let’s go back to our trusty example — the table.

As we saw, the table name is a concatenation of the namespace, database and table name, in this order. Therefor, if we want to find all tables in the test namespace and test database, we would look for all keys of the form /*test*test!tb[table_name] . This can be translated into a range by looking for any character where the table name should be. In technical terms this means looking for all hex values from 0x00 to 0xff.

This is exactly what Surreal does!

Each item (table, fields, etc.) has two functions called prefix and suffix that allow Surreal to map the ranges for this item.

These functions are used to iterate the range and find all relevant keys (for example, where querying the info for a database).

This same method is used to query all records of a table (because the record keys can be iterated given the table name), and is the base that makes Surreal so fast!

Conclusion

Whoa! We looked at a lot of details under-the-hood today.

Let’s recap:

1. Surreal stores all data (both the database structure and the data itself) in a Key-Value store
2. The keys are built using a concatenation of all the previous database layers (for example, table keys include the database and namespace)
3. This structure allows Surreal to iterate over all the items inside an object (e.g. tables in a database or rows in a table)
4. The values are a serialized using MessagePack in order to save storage.

This is the heart and soul of Surreal, and is the reason Surreal is both so flexible and so performant, both of which make SurrealDB such an innovative project and a database for the future.

Want to read more? All SurrealDB stories are available here.

Please clap if you liked the content and follow for more content. Let me know in the comments what else you would like a deep dive into.

See you next time!