Databases are the endgame for data-oriented design

For the first SpacetimeDB blog post, I’d like to clear up some confusion that I’ve seen arise in discussions about SpacetimeDB and address some general misperceptions about databases.

My sense is that many people understand databases to be “a way to store and query data which is persisted to disk” and that the relational model of data, while necessary for querying data, is otherwise an inconvenience which requires us to transform our data into a form which can be used in our general purpose programming languages.

By the end of this blog post, I hope that you will agree that not only do databases go far beyond managing persistent storage, but that they offer a principled system for organizing program memory in general and offer a general purpose solution to the performance and data modeling problems that data-oriented design and ECS were invented to solve. As the title suggests, I argue that databases are the logical conclusion you arrive at if you push data-oriented design as far as it will go.

I have generally found that most computer science was done by 1970, and if you think you’ve come up with a new clever idea, probably check the 60s again. It turns out Ted Codd had it right in 1969 and we’ve been disregarding his work at our own peril ever since.

What is data-oriented design

If we want to know how databases and data-oriented design are related, then we first need a basic understanding of data-oriented design.

Data-oriented design (DOD) is a programming paradigm that focuses on the efficient and flexible organization, processing, and storage of data. It was originally developed for use in games since games are extremely complex and interconnected systems with very high performance requirements and latency sensitivity. In short, the “normal” programming strategies (especially Object-oriented Design) weren’t cutting it.

At its heart is the honest recognition that the ultimate purpose of any program is to transform data from one form to another, and that we should seek to do this transformation in the most efficient way possible. For example, if you are writing a graphics program, you need to transform data from a scene representation to graphics buffers which are sent to the GPU. If you are writing a compiler you need to convert the program from text to a structured binary executable, and so forth.

A major component of DOD is taking into account the physical realities of computer components to determine the most efficient mechanism for performing those transformations. For example, DOD emphasizes efficient data layout in memory, aiming to minimize cache misses and ensure data is stored contiguously. This approach improves performance by leveraging the cache hierarchy of modern CPUs more effectively.

This is of course just the tip of the iceberg for techniques in DOD. I recommend Richard Fabian’s fantastic book on the subject if you’d like to learn more.

ECS (Entity Component System)

ECS is a programming pattern that is often associated with DOD which was developed to allow people to create more complex and higher performance games. The idea is to achieve two main goals:

1. Provide a data model which allows for complex data interactions while allowing for future feature additions or refactorings.
2. Provide an efficient way to arrange data in memory to take the most advantage of the CPU cache.

In the ECS pattern, these goals are achieved by creating a unique identifier to represent “entities” (sometimes called “objects”, not to be confused with OOP objects) in a game. Those identifiers are then made meaningful by associating pieces of data, called “components”, with those identifiers. Several components can be composed together on an entity to create complex data representations. Systems are transforms (code) that operate on entities with a certain set of components. For example, we could imagine a basic ECS with the following components.

Note

NOTE: I’m using Rust syntax for this example, but the concept is language agnostic.

/// This is the “entity” identifier
struct Entity(u32);

/// This is a “component”
struct Position {
    x: f32,
    y: f32,
    z: f32,
}

/// This is a “component”
/// Yes I am aware that you would not normally have a separate type
/// for position and velocity.
struct Velocity {
    x: f32,
    y: f32,
    z: f32,
}

/// This is another “component”
struct Player {
    username: String,
}

/// This is another “component”
struct Enemy {
    target: Entity,
} 
    

And we could imagine transforming this data with the following system:

/// This is a “system”
fn update_position_system(entity: Entity, position: Position, velocity: Velocity) {
    position += velocity;
} 
    

NOTE: The function above operates on a single entity at a time, although the idea is that this function will be run for every single entity that has a Position component and a Velocity component every frame. Also note that I’m omitting the plumbing to set up calling the system on each entity as this is typically provided by the particular ECS framework. Managing this is a major part of what ECS frameworks provide.

The API might be something like ecs::register_system(update_position_system), type system wrangling details notwithstanding.

Note that because ECS was built for games, there is an implicit assumption that your program executes data transforms during “frames”. A frame being a fixed length duration of time in which every system is executed on every entity that it matches.

The power of the ECS data model is that the behavior of an entity is not determined by code written for a specific kind of entity, but rather by systems (aka transforms) which operate on entities that “match” the set of components which is relevant to them.

In this way, the behavior of an entity can be changed simply by adding or removing components which alters which transforms the entity is affected by. Behavior is changed through component composition, rather than inheritance.

For example, in our small ECS above, all entities with a position are moved regardless of whether or not they are players or enemies. The basic assumption of the update_position_system is that the position and velocity components are the only data required to move an entity in our world. In reality, you may have many systems which match different subsets of components. The act of a system “matching” a set of components, can be thought of as that system “querying” all the data in the program and running on all entities matching that query, just as we did with Velocity and Position above. In fact, many ECS systems actually refer to this as “querying”, for example FLECS or Bevy.

Note that in many cases, systems only allow querying the data in a very specific way, namely, you can query for entities which have all of the components in the query. FLECS is a notable exception, as it implements a more general query system inspired by databases which I will discuss a bit further down.

Note

SPOILER ALERT: This is an inner join on the entity id.

Note that ECS can be made quite performant on modern CPUs by storing components contiguously in memory and clustered together with other components which are also queried together so that, as one entity is processed by a system, the components for the next entities are being prefetched or are already loaded into cache.

ECS is a weak-sauce relational model

Maybe the title of this section is a little spicy, but once you see it, you can’t unsee it. Once you begin using ECS you almost immediately find that you can’t represent certain constraints or relationships in your data or that modeling certain kinds of data feels awkward or shoehorned into the data model.

For example, how would you model chat messages in your game? I suppose you’d have to represent that as an entity in your game. How would you represent a constraint that would prevent a health component from being added to your chat message erroneously? In ECS it’s straightforward to create a system which operates on chat messages individually, but how would you query your chat messages so that you can display them in order? How would you model an entity which has many instances of the same component? How would I model a friends list where all players have many friends who are also players?

It’s clear that the ECS data model is quite powerful for modeling certain types of data, like entities in a game world, but is not quite general enough to model all types of application data. What at first appears to be awkwardness or annoyances is actually a fundamental limitation of the ECS data model.

So I raise the question: is there a data model, similar to the ECS data model, that has proven itself capable and general enough of representing all manner of application data for over 50 years of software development?

You bet there is!

Implementation details aside – although we’ll get to that too – at its core the ECS data model is baby’s first relational model. More precisely, the ECS data model is a strict subset of the relational model; relations can represent everything in the ECS model plus more.

We can demonstrate this by implementing the ECS data model within the relational model. We can translate ECS to the relational model by representing entities by an Entity table with a single column:

CREATE TABLE Entity (
    id SERIAL PRIMARY KEY
); 
    

Next we can represent each component as a table with a foreign key constraint on the entity_id.

CREATE TABLE Position (
    entity_id INT PRIMARY KEY,
    x FLOAT,
    y FLOAT,
    z FLOAT,
    FOREIGN KEY (entity_id) REFERENCES Entity(id)
);

CREATE TABLE Velocity (
    entity_id INT PRIMARY KEY,
    x FLOAT,
    y FLOAT,
    z FLOAT,
    FOREIGN KEY (entity_id) REFERENCES Entity(id)
);

CREATE TABLE Player (
    entity_id INT PRIMARY KEY,
    username TEXT,
    FOREIGN KEY (entity_id) REFERENCES Entity(id)
);

CREATE TABLE Enemy (
    entity_id INT PRIMARY KEY,
    target_entity_id INT,
    FOREIGN KEY (entity_id) REFERENCES Entity(id),
    FOREIGN KEY (target_entity_id) REFERENCES Entity(id)
); 
    

Note

NOTE: I am using PostgreSQL to represent these relations because many people are familiar, but any relational representation will do, and arguably SQL is quite a poor one.

Once we break it down this way, it’s pretty easy to see that the ECS model is just the relational model with the following restrictions:

1. There is an entity table with a single unique id column.
2. All other tables must have a unique, foreign key reference to the entity id.
3. Systems (aka queries) must execute on every entity they match, every “frame”.
4. Systems may only execute and operate on INNER JOIN queries on the entity id.

That’s really all there is to it. This is now identical to the ECS data model. Restriction 3, in particular, is interesting because it implicitly assumes that your program’s logic must have a scheduler which runs all queries multiple times per second at fixed intervals. That’s a common need for some games, but certainly not all games and definitely not most other types of applications.

As an aside, I would like to point out that notable ECS implementations, such as FLECS, are working towards eliminating, or have already eliminated restriction number 4 by adding in more expressive query engines into their frameworks. In fact, FLECS is especially notable for this because it uses a variant of Datalog which in its recursive form is strictly more expressive than the relational model which is based on first-order logic.

Please note, I’m not an expert on first order logic or Datalog and I’d love to see some discussion about this. This blog post from Sander Mertens, the creator of FLECS, is particularly enlightening, although I wholeheartedly reject the statement that “database[s]... are, put plainly, too slow.”

Why not go further though? Why not free ourselves completely from the shackles of these restrictions? Why not embrace the full power of the relational model?

The keen amongst you are probably crying out that it must be the details of how ECS is implemented and optimized for games that make it more performant than a general purpose database in the context of games. After all, databases are slow, and ECS is fast! Databases have all kinds of other requirements like transactions and ACID constraints! How could a database ever process and update millions of entities per second?

That is where you’d be mistaken… mostly.

Databases aren’t slow

Databases are perhaps the most performant, well optimized, highly multithreaded programs ever written. There has been 50+ years of research applied to the problem of executing queries on row formatted data. The problem has been studied from almost every conceivable angle: high throughput, low latency, high write volume, high read volume, large rows, small rows, locking, lock-free, single version concurrency control, multi version concurrency control, strict transaction isolation, loose transaction isolation, you name it.

I think that people perceive databases to be slow, not because they are slow, but because they often interact with them in the context of persisting data to disk, from across a network, by passing strings back and forth which must be parsed, compiled and executed. If you’ve ever optimized a program, you know that I just listed pretty much the slowest operations you can do on a computer.

It turns out that an enormous amount of research has focused on in-memory databases, and that many of the optimizations that are built into ECS are already employed by certain databases in a configurable way. For example, consider “archetype”s in ECS. Archetypes are an optimization whereby entities which share the same exact set of components are stored in the same physical location. This allows an ECS framework to satisfy a system’s predicate without having to filter rows that are missing certain components. It turns out that certain database systems already implement this optimization as a “pre-join” operation at the storage layer. That is, they physically store the tables pre-joined if these kinds of operations are common or this is manually configured by the user. Another similar technique is creating a materialized view, although that requires making a copy of the data.

Another common optimization in ECS is to divide the work of a given system onto multiple cores by partitioning a group of entities onto each core and processing them separately. This is commonly referred to as a parallel query and is particularly suited to updating many rows in a single query, just as is the case in ECS.

There are database systems that easily achieve millions of transactions per second for in-memory data. For example, consider Cicada:

It handles up to 2.07 M TPC-C transactions per second and 56.5 M YCSB transactions per second, and scans up to 356 M records per second on a single 28-core machine.

For the record, the Yahoo! Cloud Serving Benchmark (YCSB) is a framework for evaluating the performance of various types of databases, particularly NoSQL systems. The TPC-C benchmark, developed by the Transaction Processing Performance Council (TPC), simulates a complete computing environment where a population of users executes transactions against a database with a combination of common types of queries.

Or consider HyPer, which can achieve nearly a million serializable transactions per second. These are truly incredible numbers, particularly when you consider that this is an apples to oranges comparison - databases are more flexible and provide stronger ACID guarantees than an ECS.

Databases are much faster than you think.

Where do we go from here?

It is of course the case that the additional constraints of ECS allow you to make different optimizations that will allow ECS systems to outperform database systems in certain scenarios. Notably, databases which are designed to provide transactional semantics will always have overhead related to providing those guarantees.

My central thesis is that this is beside the point. My real point is that viewing our programs as databases gives us a structured framework within which to evaluate them. It provides a general and structured way to represent and transform our app data, a framework in which we can pick and choose which features and performance tradeoffs make the most sense for our particular application, and a framework by which we can evaluate the performance of our systems against standardized metrics.

The ECS community seems to be moving in this direction already and I couldn’t be more excited to see where it goes.

Here at Clockwork Labs, we’re putting our money where our mouth is. Our MMORPG BitCraft is implemented 100% as a WebAssembly stored procedure inside of our real-time, low latency, in-memory database, SpacetimeDB.

This is what a typical SpacetimeDB stored procedure function would look like:

/// NOTE: If you’re looking for the `join!` macro in our current docs, we haven’t added this functionality as of `v0.7` so you’d have to join manually in this case.
#[spacetimedb(reducer)]
fn update_position_system() {
    for (position, velocity) in join!(Position, Velocity) {
        position += velocity;
        Position::update_by_entity_id(position.entity_id, position);
    }
} 
    

As you can see, this is just regular ECS implemented in the relational model and it’s how we run the entire game. I hope you agree that this idea doesn’t seem quite as crazy as it might have at the beginning of this post.

For so long, we’ve all taken an unprincipled approach to the pile of pointers and loose data in the runtime of our programs. The philosophy of data-oriented design is centered around the idea that transforming data is the ultimate purpose of any program. I think it’s about time we took that idea seriously and learned from the people that have taken that idea seriously since 1969. We’re in the endgame now.

Credits

• Thank you to Sander Mertens for the interesting discussions on this topic.
• Thank you to Phoebe Goldman for inspiration and review of this post.
• Thanks to Richard Fabian for writing such an inspirational book.