Background and introduction to the immutable, deterministic data storage in sijo-ion

The code is located here: https://codeberg.org/simendsjo/sijo-ion/. It is very much experimental and will certainly not compile on another machine as some libraries/patches haven’t been made publically available.

Back in 2015 I was working on an internal expert system. Parts of it was quite nice to work with being Event Driven and using the Command Query Responsibility Segregation pattern. The main problem was that the events were the primary data store (and stored immutably).

Large events containing all necessary data is nice for consumers, but not easy to work with as the primary data storage. All the issues with this design is out of scope for this post, but it’s safe to say that bugs occur, misunderstandings happens, requirements change, users makes mistakes, third party data has bugs etc. Data is the single most important thing our systems have, so we have to take care to make sure it’s possible to correct, redesign and extend. … but again, these issues are out of scope for this post.

When designing a new feature, I tried going the exact opposite direction using many small events. Each event was basically just a triple of the entity, the field and the value. This allowed me to easily add new fields without redesigning existing events (did I mention the events were immutable and the primary data source..?)

But this got me thinking. Could we just have generic (entity component value) triples and model everything using this? Metadata could be attached in the same way. Complex values could be property lists or an id to another entity.

Could this be our primary data storage?

After experimenting with my triples, I found out a very similar pattern is actually quite widely used in game development and known as Entity Component System.

The entity is the game object, usually just an identifier, a component is the type of value (health, position, velocity, ..) and the value is the component value for the entity.

A system is a process which acts on entities which matches some set of components. E.g. a physics system might act on anything with a position and velocity to update the position each game tick.

For game development needs, related data is stored together in contiguous memory to allow fast access and avoid following pointers around.

I didn’t really care about the performance, but rather the flexibility of the design. But I had been drinking the functional programming cool aid and fallen in love with immutability. Having an immutable data storage was an important design goal.

I experimented with F#, Racket and Guile, but eventually chose Common Lisp. The F# type system didn’t yield any benefits for the open system I wanted, and I found it difficult to get the necessary performance from Racket and Guile. Both of these languages are much faster today, but Common Lisp is still a good choice.

Game development is not traditionally considered very deterministic, but when it is actually very simple to make deterministic opposed to many business applications which usually integrate with external systems.

As my experiment involved a game, it doesn’t need access to the outside world. This means I have all state in my application, and the only unknown is user input.

By storing the pseudo-random state in my world state, I have a fully deterministic system. This also means I only need to store the initial random number seed, and each player command after it has been executed, e.g. (dwim-direction 'the-player :north) which does the sensible thing up (attack, move, etc.)

I don’t need to store anything more than the player commands to allow a full replay of the game state, but this is way too high level to act upon.

In the above case, (dwim-direction 'the-player :north) will get picked up by the player actor. If an enemy is in that location, an attack action is issues. This is handled by the attack actor, which might result in a damage action and so on, maybe ending in a death action.

Handling each of these might also modify the state though, and this is done by setting these triples. There is ('value-set entity component value) and ('value-removed entity component value), and these two entries are the data store.

I plan to avoid the value-set / value-removed by using a special value which means we should remove the component from the entity, e.g. 'ecs::%remove-component.

Based on these two entries, we build up indices as maps: entity -> component -> value and component -> entity -> value. These indices are used in the EDSL query language to select entities.

While the core data resides in my immutable store, some data is more difficult to store there for performance reasons. The animation system is based on a traditional ECS using mutable state to change the positions. When a turn is finished, we look at the audit log for that turn, and extract things like movement to register animations. The animations are pushed to the traditional ECS through a channel.

This means the render loop easily runs at 500+ fps on my laptop while animating all entities. I of course expect this to drop, but I think 30 fps would be enough for a turn-based game like this anyway.

As the system is immutable and deterministic, I can easily implement time traveling. Together with a dynamic environment like Common Lisp, this yields an enormous productivity boost.

I have a hotkey which rewinds to the previous state. When I want to change some behavior or fix a bug, I rewind the state, change the code, compile the changed functions, and execute the same command again. I do this until I’m happy with the new behavior and can continue to the next task. The turnaround time goes from minutes to seconds.

So far, the above has been working quite nice, but there is no free lunch. Querying data like this might require following a lot of pointers. I implemented some quite sophisticated multiple level caching, but disabled it as cache invalidation was difficult. When an component value changes, how can I find all the queries which must be invalidated given that this component was on the path and not the resulting component? And hopefully only invalidate part of the data?

Cache invalidation is hard, and it might require more tagging and book-keeping to work properly. For each value stored, maybe I need to know the entire path to a value to evict it from the cache?

Purity, immutability and determinism is wonderful properties to have. The Common Lisp condition system which doesn’t pop the stack is amazing. And being able to just recompile functions and keep going is magical.

I find it really hard to go back to mainstream programming languages after working with something as powerful as Common Lisp. Sure, they might have larger communities and more libraries, but they are light years away on so many aspects.

I hope to find some time to pick up the project again to play more around with these ideas, and I might write more posts for other parts of the system.