Building an ECS #3: Storage in Pictures

12 min readSep 14, 2024

In my previous “Building an ECS” articles I used code examples to explain a few things. This time I’m going to use pictures to explain many things about how Flecs stores game data. This will (hopefully) give a more intuitive and holistic understanding of the internals of an Entity Component System, even if I’m skimping a bit on details here and there :)

I’m assuming basic knowledge of Entity Component Systems, if you’re fuzzy on the details, check https://github.com/SanderMertens/ecs-faq

In the spirit of show don’t tell, let’s get into it!

Archetypes (1/14)

An archetype is much like a database table, where each row is an entity, and each column is a component. Other than a database table though, entities are only ever stored in a single archetype. As a result, this archetype contains all components for its entities.

The following diagram shows an archetype with entities (e1, e2, e3) where each of these entities have exactly two components (Position, Velocity):

Let’s explode the archetype into its individual parts:

Component id array: this is an array where each component id is stored exactly once. The array is sorted, which speeds up ECS operations.
Entity id array: this array provides quick access to entity ids when iterating components in the table.
Columns array: this array stores one array (“column”) per component. The elements line up with the component id array.
Component columns: columns store the component data. The elements line up with the entity id array.

The above diagram shows an example of SoA (“struct of arrays”) storage. Another option is to use an AoS (“array of structs”) storage:

Here, the entity id and all of the components are stored in a row of a single big array (or sometimes in multiple “chunks”). The rest of the article assumes SoA storage, as this the most common form of storage.

Archetype Moves (2/14)

When a component is added to an entity, it is moved to a different archetype. This means that all components of the entity need to be moved as well. Let’s take a look at what happens when we add component Mass:

Note how the move left an empty spot in the [Position, Velocity] archetype. This needs to be patched up, or queries will be reading garbage data. The solution is to move e3 to e1’s old row, and delete the last row:

Let’s take a look at what happens when we remove Mass again from e1:

Note how similar this is to adding a component! Also note that since we didn’t leave an empty spot in between entities this time, we don’t need to do any additional moving.

The Archetype Graph (3/14)

Before we can move to another archetype, we first need to find it. The archetype graph is a data structure that was first introduced in Flecs to speed up this search.

The idea is simple: each archetype is a graph node, and edges between nodes represent the components that have been added & removed:

When a component is added but no edge exists, we do a (more expensive) lookup first, then create a new edge for it. This means that over time archetype traversal becomes more efficient as more edges exist!

An advantage of the archetype graph is that we can encode invariants on the graph edges. If component Power always comes with component Responsibility, we can encode this on the graph like so:

This is how the With trait works in Flecs, and it lets us add multiple components for the cost of one archetype move!

Exclusive relationships also use the archetype graph in a special way, where following an edge replaces a component:

What’s nice is that this is an atomic operation: an application can never observe an entity temporarily having two (or no) parents.

Tags (4/14)

Tags (also called ZSTs or zero sized types) are components that have no data. Examples of tags are Npc, Archer, IsAttacking and Idle. In Flecs, tags are not stored as archetype columns. This has two advantages:

It saves (some) memory.
Tags are free when moving entities between archetypes.

Here’s an archetype with a tag. Note how it only has two columns:

This presents a problem: the component id array no longer lines up with the columns, which makes it difficult to tell what a column’s component is. To fix this we add a new column map array:

This array maps indices from the component id array to the columns array. A negative value in the array means that the component id does not have a column - e.g. it is a tag.

Sometimes we want the opposite: go from a column to a component id. Doing the mapping in reverse lets us do this:

In the extreme case of an archetype with only tags, this optimization turns moving archetypes into a constant-time operation! This can be useful, especially in relationship-heavy use cases. Speaking of:

Relationships (5/14)

Relationships can be a complex feature to implement, but for the archetype storage they are actually a pretty minor extension. The following diagram shows an archetype with relationships:

Note how similar these relationship pairs look to tags! That is because for all the storage cares relationships are just large component ids. That means that we can just as easily store relationships with data:

There’s a bit more logic involved in figuring out which type belongs to a pair, but other than that this is pretty much all there is to storing relationships!

Sparse Components (6/14)

A component can be marked as “sparse” in Flecs. This means it will use a sparse storage, as opposed to the “dense” archetype storage. The following diagram shows an archetype with a sparse Velocity component:

Note how Velocity in this archetype looks just like a tag. Sparse components are stored outside of the archetype, so they don’t need to be moved when moving the entity.

The following diagram shows the sparse component storage for Velocity:

There’s a lot going on here, so let’s take it apart bit by bit:

Dense array: Stores the entity ids that have the Velocity component.
Sparse array: Stores the component data, and is indexed by the entity.
Dense index: Points back to an element in the dense array.
Tombstone: Element 0 in the dense array is not used, so that we can use dense index 0 to indicate that an entity doesn’t have the component.
Element 0 in the sparse array is never populated because 0 is used by Flecs to indicate an invalid/non-existing entity.
To get Velocity for entity e2, we can do sparse_array[2].

Sparse components are guaranteed to not move around in memory, which means the sparse array cannot be resized. To accomplish this the storage uses paging which breaks the sparse array up into fixed-sized blocks:

Callout to EnTT, which heavily inspired the design of the sparse storage!

Disabled Components (7/14)

In some cases it can be useful to prevent a component from getting matched by queries, without removing it from the entity. This can serve two purposes:

We can restore the old component value at a later point in time.
It saves performance as the entity doesn’t need to change archetypes.

In Flecs components can be disabled and enabled like this:

e.disable<Velocity>();
e.enable<Velocity>();

Let’s take a look at how disabled components are stored:

A few things jump out:

The component id array contains a TOGGLE | Velocity component, which indicates that Velocity can be disabled for this archetype.
TOGGLE is a “type flag” which can be added to any component id
A bitset indicates which Velocity rows are disabled.
To enable or disable a component we just need to flip a bit.

A bitset is an id of booleans, but instead of storing each boolean as a single byte, it is stored as a bit. CPUs can evaluate 8 bytes (or 64 bits) in a single instruction, which means queries can evaluate 64 entities in just one check!

Here’s an archetype with multiple toggle-able components:

Union Relationships (8/14)

Relationships have a tendency to fragment entities into many different archetypes if left unchecked. Union relationships remedy this, by storing entities with different relationship targets in the same archetype. This makes queries for union relationships a bit slower, but all other queries faster! Here’s an archetype with a union relationship:

Note how instead of showing (Movement, Walking) or (Movement, Running) the archetype has Union as target of the relationship pair. This indicates to Flecs that the archetype stores a union relationship.

The targets are stored in an external data structure called a “switch list” that has been purpose built for union relationships:

Without getting into too much detail, a switch list achieves these goals:

It can quickly iterate all entities for any target.
It can quickly iterate all entities for a specific target.
It has O(1) insertion/removal.
It has O(1) lookups.

The target array in the switch list is indexed by the entity id. To conserve memory when working with large entity ids, the switch list uses paging in a way that’s very similar to the sparse component storage.

The Entity Index (9/14)

The entity index tells us in which archetype and at which row an entity is stored. Additionally, the entity index stores which version of the entity is currently alive. The following diagram shows the entity index:

0 elements in dense/sparse arrays are omitted for brevity

Note how similar this diagram looks to the sparse component storage- that’s because this is also a sparse set! Let’s go over the different parts of this data structure:

Dense array: stores all entities that have been created by the world.
The dense array is split up in two sections: one for alive entities and one for dead (recyclable) entities.
An alive_count tracks how many entities in the dense array are alive.
Sparse array: is indexed by the entity id. Entity e1 is stored at sparse_array[1], e2 is stored at sparse_array[2] etc. sparse_array[0] is not used, as 0 is used to indicate an invalid entity.
The sparse array stores the index of the dense array where the entity id with entity version can be found.
This check tells Flecs whether an entity is alive: dense_array[sparse_array[entity_without_version].dense] == entity.

Deleting Entities (10/14)

Let’s see how the entity index changes when we delete entity e4. Everything in yellow changed:

Here’s what happened:

e3 and e4 swapped places in the dense array.
The indices in the sparse array were updated to reflect this.
The alive_count has been decreased by 1.
The archetype/row got cleared in the sparse array for e4.
The version of e4 got increased from v1 to v2.

Some sparse set designs do not have a swap-on-delete, and can therefore achieve slightly better delete performance. However, this design has significant benefits when:

Recycling Entities (11/14)

Let’s now see what happens to the entity index when we recycle two entities. Everything in yellow has changed:

The alive_count was increased by 2.
The archetype & row were updated for e2 and e4.

Note how, apart from updating the entries in the sparse array, this lets us effectively recycle any number of entities in a single constant time operation, as long as enough dead entities exist!

Entity Partitioning (12/14)

Partitioned ids can be used to efficiently determine whether entities belong to a specific group. A typical use case for this is networked games, where local and remote entities are created from different id ranges.

This does create a challenge for the entity index. An application might want to reserve the last bit in an id for networked entities, which means that ids can get very large. If the sparse array had to accommodate for the largest entity id, we would quickly run out of memory.

The solution is to use a paged sparse set, similar to the one used for sparse components. With paging we only need to allocate sparse arrays for id ranges that actually have entities:

The Component Index (13/14)

The component index is a data structure that was first introduced in Flecs to quickly find all archetypes with a specific component. The following diagram shows the component index:

Component map: maps each ECS component to an archetype map.
Archetype map: contains all archetypes that have the component.
Archetype record: contains information about where in the archetype the component can be found.

The component index can be used to answer two kinds of questions:

Which archetypes have Position?
Does archetype X have Position?

This makes the component index useful for evaluating queries. To find all archetypes that match query “Position, Velocity”, we can first use the component index to find all archetypes with Position, then check if each of the resulting archetypes has Velocity. This is in essence how uncached queries work in Flecs.

Wildcard Queries (14/14)

Wildcard queries can do things like “find all entities that like anyone”, which would look like (Likes, *). This would return entities with (Likes, Bob), (Likes, Alice), (Likes, Pizza) and so on. How can we use the component index to find all archetypes with (Likes, *)?

To solve this, we can add an entry for (Likes, *) to the component index that contains an archetype map with all archetypes that have a Likes pair:

Now we can easily get all archetypes with a Likes pair by iterating the archetype map for (Likes, *). What this doesn’t tell us however is how many Likes pairs the archetype contains, which is important information if we want our queries to return all matching pairs.

This can be addressed by simply adding a count member to the archetype record. For regular components this count will always be 1, but for wildcards the count can be higher. An example:

Here index is the location of the component in the archetypes’ component id array, and count the number of occurrences of the component.

While it may not look like much at first glance, this data structure is at the core of evaluating the advanced queries described in this article.

Concluding…

Building a functional ECS is not difficult, but building an ECS that performs well under a wide range of scenarios is a fun rabbit hole that you can spend years on! I hope this article lifted the veil a little bit on what goes into writing one, and helps anyone looking to build their own :)

Look forward to more of these in the future, as there are many more topics to cover, such as storing hierarchies, command batching, evaluating complex queries, reactivity, multithreading and so on!

If you liked this article, consider giving Flecs a star: https://github.com/SanderMertens/flecs

If you’d like to discuss ECS in more detail, join the Flecs Discord: https://discord.gg/Kw9KcvP8ZK