lud
Architecture for updating multiple states in isolation with implicit locking
Sorry for the title, I did not know what to write.
Hello,
I’m trying to build an architecture for a game. In the game, there are
starbases which are basically event processors: they have a state,
receive different events and update their state accordingly.
I do not want to have a process per starbase because it will be many
of them, and they are idle most of the time. For example, they have
production lines: when a production of food is started, I calculate
the time of the production end, and I will send an event to the
starbase at this time. Durations can be in minutes so I have no use
of idling processes for several minutes. Also states take memory.
However I want all events for a given starbase to happen sequentially,
because I will load the state from database, handle the event, and
write the state.
So, what I plan to do is to have a worker pool and use
erlang:phash2/2 to hash the id of my starbase and send all events
for a given starbase to the same worker. This should be enough to
prevent concurrent read/write of the same state and work sequentially.
(A small word on distribution : if I have to work on different nodes,
those would represent solar systems, or solar system clusters, so a
given starbase will always be handled on the same node.)
If you think this is a bad design, i think you can skip the rest of
this post, and please tell my why.
Now, I have to update several starbase at a time, for example to
conclude a trade. Starbases declare what they need to but and what
they want to sell. I have some code running to figure out matching
orders. When I match is found, I want to run a task on a worker to
load both states, check if orders are still matching, update states
(mark orders as fullfilled, exchange money, move goods from the
“selling” cargo to the “sold-and-waiting-to-be-carried” cargo space).
The problem is that this task will run on the worker for starbase A,
and starbase B could be concurrently updated with another event that
will consume goods in cargo.
I am looking for a solution that could handle tasks for any amount of
starbases, not just 2.
So this is my current plan:
- Hash all the keys (starbase ids) to find the workers. If all keys
give the same worker, just run the task as a single-key task. - With multiple workers, fetch the pid of the workers, take one pid
as:masterand other pid(s) as:slave. - Run an inner task on the master worker: pass the slave keys
(starbase ids) to it, then the worker will wait for anackmessage
with those keys and the slave pids from all slaves. - Run an inner task on each slave worker: pass the master pid, the
worker will send theackmessage with the slave key to it. Then,
wait for a:finishedmessage. All messages will be tagged with
the same ref to identify the event and have selective receives. - At this point, states cannot be changed by other events.
- When the master received all acknowledgements from the slaves, run
the actual task (i.e. load states, handle the event, write states),
then send the:finishedmessage to all slave pids.
It seems a bit complicated, no ? The main problem is to make workers wait doing nothing to provide locking.
I have another approach with a mutex I wrote that can lock multiple
keys without deadlocks, but that would require to lock the keys for
all tasks, even the single-key ones, so a lot more message passing and
a bottleneck on the mutex. I expect to have way more events for a
single state than events involving multiple entities.
Most Liked
al2o3cr
IMO worrying about this is premature; there are a lot of other problems you’ll need to solve before this particular one needs optimization.
What you’re describing with ack and finished messages sounds a lot like two-phase commit; there’s a substantial literature describing different approaches to solving that coordination problem.
The theme of your game has me wondering: should these interactions be instantaneous? The speed of light is already an issue in modern distributed systems, and interstellar distances (even with silly-fast FTL communication) would make it even more so.
Another thought: some real-world transactions are coordinated through escrow services. What about setting up something like that? A possible process:
- party A wants to buy 1000 widgets from party B for a total of $10000
- party A transfers the $10000 to the escrow service
- party B transfers the 1000 widgets to the escrow service
- the escrow service releases the money and the widgets
In a system context like this, you’d typically have the “transfers” above include a timeout so that if the escrow doesn’t complete the resources eventually revert to their original owners.
One note: the name escrow service shouldn’t be read as implying there’s one process doing this. It would seem simpler to spin up a new process per escrow interaction, to keep the state machine straightforward.
Fl4m3Ph03n1x
In Elixir you can have thousands and even millions of processes in a machine, BEAM is highly optimized and the amount of resources they cost is minimal.
As for state taking up memory, why would this be an issue? Your application needs state somehow, you will have to save it somewhere.
Ahh, cunning solution. I like it 
So, from what I can understand, your problem is that when you make a transaction, between several nodes, that transaction needs to be atomic in the sense that no other operations can take place while the transaction is happening so you can avoid inconsistent states.
This is a tough problem, but one with many solutions. One of way avoiding state on workers would be to have your state on an ETS table, and then have a mediator that changes and updates state for all processes. This mediator would eventually become a bottleneck but it would also serve as a point of synchronization in your system. (Regarding bottlenecks, always benchmark first! A mediator will only be a bottleneck if it handles more messages than it can get!)
Another possible solution would be the use of optimistic locks. Locking in DBs is a world on it’s own, but I find that optimistic locks, besides having great performance, do work in a lot of cases when you have few collisions:
Aside from that, the only remaining solution I can think of is defining a worker communication protocol, which you already have defined and explained in your post.
Anyway, hope it helps somehow!
lud
Hi,
In Elixir you can have thousands and even millions of processes […] Your application needs state somehow, you will have to save it somewhere.
Thank you for your answer. I know that I can have more processes than I would ever need, but yes the main problem with that is memory. It is a game so state can be pretty complex, and I do not want to have thousands of starbases state idling for nothing. With this architecture I can keep a low memory profile. Actually I could have processes that hold state for faster read/writes (instead of database/disk) and shutdown with a timeout ; wether the state is written to a transient GenServer with timeout / an EST table or directly do disk (I’m going to start with that) is another question I believe, the main problem beeing queuing updates and multi-state transactions.
Another thing with processes is errors handling. If I want to act on two states and rollback on errors, my state-holding-update-handling processes will need a way to cancel the last update, or at least a savepoint/commint mechanism. Whereas handling the two states update in a single process and rolling back is just a matter of not saving the new states.
So, from what I can understand, your problem is that when you make a transaction, between several nodes, that transaction needs to be atomic in the sense that no other operations can take place while the transaction is happening so you can avoid inconsistent states.
Not nodes, just states. Everything that I describe will happen on a single node. But yes, it is a transaction/concurrency problem. A mediator would be kind of equal to have only one worker. It is simpler, that is true, but I like the idea of having concurrency there. Maybe that is my mistake.
Optimistic locks are interesting and may be applicable in my case, I will research on that point.
Thank you very much.
dimitarvp
Sorry I can’t be more useful but just as a quick pointer, this latest ElixirRadar article was extremely interesting:
I know you’re not doing Phoenix in this case (or I think so) but Horde and DeltaCrdt are amazing and under-appreciated libraries doing a good chunk of what you intend to do.
Popular in Questions
Other popular topics
Latest on Elixir Forum
Sponsor Spotlight
Catch errors, track performance, monitor hosts and more.
Categories:
Sub Categories:
Forums
Our Sponsors
Build Elixir applications with speed and confidence.
Supporting innovation across the BEAM ecosystem.
We build reliable cloud platforms for business-critical systems.
Catch errors, track performance, monitor hosts and more.
Practical resources that improve the lives of professional developers.
Develop your skills with books, videos, and courses.
Producing high quality Elixir screencasts since 2017.
Courses that'll move you from confusion to "Aha, now I get it!"