I have tweeted a while ago about the fact that Audiotool does heavily rely on a so called software transactional memory. In this blog post I want to discuss the implementation of our STM and why it is useful.
Wikipedia defines STM as:
In computer science, software transactional memory (STM) is a concurrency control mechanism analogous to database transactions for controlling access to shared memory in concurrent computing.
First of all when reading this you might think that an STM is not necessary since ActionScript does not support true concurrency and also the shared-nothing worker proposal will not allow you concurrent memory access. While this holds true you may not forget that concurrency becomes an issue when you have just access to a single core but on multiple machines.
A lesser known fact about Audiotool is also that we have a built-in system for real time collaboration since its beginning. Due to conceptional issues and other prioritized features we were never able to roll it out as a full feature but the technology base is there.
When it comes to multiplayer gaming and network latency you will always have to figure out a system which allows you to share a certain state across multiple machines. In some games the state is synchronized across a certain server. An example is an FPS like Quake3. The Audiotool is unlike Quake3 not a FPS and different conditions have to be met. And this is the reason why I have choosen to implement an STM with very optimistic concurrency control.
The basic idea of my system is to use atomic transactions with commit and revert operations. Those are handled by a transaction manager which performs the basic tasks of an STM. That means: execute all transactions until an error occurs, roll back and try again. Each transaction in the Audiotool contains a guard. The guard defines whether or not one should still execute the transaction.
Here is an example of why a guard is important and how all this stuff works. You have two Audiotool instances running that share the same state. We call them A and B. A and B are connected via P2P no an arbitrary network. This means exchanging messages introduces latency and we cannot guarantee that A is at the same state of B.
So what happens? t0 is committed by A, serialized and sent to B who is committing the same transaction. The same applies to t1. t2 is initiated by B, serialized and sent to A. Everything works fine until B commits t4. While t4 is being transferred to A, A created t5 and committed it. This means A never saw t4 when it committed t5 and B would continue with t6 ignoring t5. A will actually receive t4 after he commited t5 so the system will revert t5, commit t4, commit t5 if the guard does not prevent it, and both continue at t6.
To explain the guard: Imagine the t5 transaction includes modifications on a device in the Audiotool that is deleted by t4. In that case t5 will never be executed.
So what does this imply? You can guess that each modification of the Audiotool state is in fact handled by a transaction and we carefully have to pick the guards. E.g. if an editor is referenced by a transaction it is part of the guard. However this introduces a second issue: references. Sharing references of objects across a network is a tricky task. I am using “boxes” to solve this issue. A box can hold a value and it is guaranteed that it will hold the same value at the same state across the network. A box can be serialized and will be shared between commit and revert states. This means if tn creates an object which is referenced by tn+1 both will use the same box. This also means that I can safely revert tn+1 and then tn and commit them without having to worry that both still reference the same object. And this even works across the network. And in fact we can now also identify whether or not one transaction would conflict with a different one which is a very important condition for the actual implementation.
Right now you might have figured out that a transaction in the Audiotool has the following properties:
- It is serializable so it can be transferred across the network.
- All object references must be stored via “boxes”.
- A guard is used to determine whether or not to commit a transaction.
- Transactions can be committed and reverted.
A lot of stuff one has to reason about. But although we do not support live collaboration at the moment we are using the STM. Why? The reason is quite simple. The STM gives us history for free. Since everything is serializable via a very lightweight protocol we can take the last 500 transactions for instance and store them as a compressed ByteArray in memory instead of each as a single object with all its references.
Another very nice option is testing. A serializable history means that one simply has to press a super secret shortcut to dump the whole history and send it to the responsible developer who can reason about every single step that happened which ultimately led to the error. In development mode I usually commit, revert and commit each transaction. Then I also serialize and deserialize them and do the whole thing again.
Since transactions are known by the system we can also write a fuzzer that executes lots of crazy stuff. Sort of Android’s monkey mode. And ultimately I personally hope that we will get to the point where we will enable live collaboration in the Audiotool of course.
The last feature I implemented is the automatic transformation of arbitrary transactions to a compound transaction. You can guess what this feature actually means for the user :). In fact it is very complex and I implemented it with the STM using only a couple lines of code (of course that is just half the story …).
If you are interested in writing your own multi user application I think this is a very nice approach since collisions do not happen very often from my experience and the optimistic concurrency in a P2P environment achieves great results in terms of overall latency and feeling. The Google Wave protocol and their operational transform is also an interesting read.
I have tweeted a while ago about the fact that Audiotool does heavily rely on a so called software transactional memory. In this blog post I want to discuss the implementation of our STM and why it is useful.
Wikipedia defines STM as:
In computer science, software transactional memory (STM) is a concurrency control mechanism analogous to database transactions for controlling access to shared memory in concurrent computing.
First of all when reading this you might think that an STM is not necessary since ActionScript does not support true concurrency and also the shared-nothing worker proposal will not allow you concurrent memory access. While this holds true you may not forget that concurrency becomes an issue when you have just access to a single core but on multiple machines.
A lesser known fact about Audiotool is also that we have a built-in system for real time collaboration since its beginning. Due to conceptional issues and other prioritized features we were never able to roll it out as a full feature but the technology base is there.
When it comes to multiplayer gaming and network latency you will always have to figure out a system which allows you to share a certain state across multiple machines. In some games the state is synchronized across a certain server. An example is an FPS like Quake3. The Audiotool is unlike Quake3 not a FPS and different conditions have to be met. And this is the reason why I have choosen to implement an STM with very optimistic concurrency control.
The basic idea of my system is to use atomic transactions with commit and revert operations. Those are handled by a transaction manager which performs the basic tasks of an STM. That means: execute all transactions until an error occurs, roll back and try again. Each transaction in the Audiotool contains a guard. The guard defines whether or not one should still execute the transaction.
Here is an example of why a guard is important and how all this stuff works. You have two Audiotool instances running that share the same state. We call them A and B. A and B are connected via P2P no an arbitrary network. This means exchanging messages introduces latency and we cannot guarantee that A is at the same state of B.
So what happens? t0 is committed by A, serialized and sent to B who is committing the same transaction. The same applies to t1. t2 is initiated by B, serialized and sent to A. Everything works fine until B commits t4. While t4 is being transferred to A, A created t5 and committed it. This means A never saw t4 when it committed t5 and B would continue with t6 ignoring t5. A will actually receive t4 after he commited t5 so the system will revert t5, commit t4, commit t5 if the guard does not prevent it, and both continue at t6.
To explain the guard: Imagine the t5 transaction includes modifications on a device in the Audiotool that is deleted by t4. In that case t5 will never be executed.
So what does this imply? You can guess that each modification of the Audiotool state is in fact handled by a transaction and we carefully have to pick the guards. E.g. if an editor is referenced by a transaction it is part of the guard. However this introduces a second issue: references. Sharing references of objects across a network is a tricky task. I am using "boxes" to solve this issue. A box can hold a value and it is guaranteed that it will hold the same value at the same state across the network. A box can be serialized and will be shared between commit and revert states. This means if tn creates an object which is referenced by tn+1 both will use the same box. This also means that I can safely revert tn+1 and then tn and commit them without having to worry that both still reference the same object. And this even works across the network. And in fact we can now also identify whether or not one transaction would conflict with a different one which is a very important condition for the actual implementation.
Right now you might have figured out that a transaction in the Audiotool has the following properties:
It is serializable so it can be transferred across the network.
All object references must be stored via "boxes".
A guard is used to determine whether or not to commit a transaction.
Transactions can be committed and reverted.
A lot of stuff one has to reason about. But although we do not support live collaboration at the moment we are using the STM. Why? The reason is quite simple. The STM gives us history for free. Since everything is serializable via a very lightweight protocol we can take the last 500 transactions for instance and store them as a compressed ByteArray in memory instead of each as a single object with all its references.
Another very nice option is testing. A serializable history means that one simply has to press a super secret shortcut to dump the whole history and send it to the responsible developer who can reason about every single step that happened which ultimately led to the error. In development mode I usually commit, revert and commit each transaction. Then I also serialize and deserialize them and do the whole thing again.
Since transactions are known by the system we can also write a fuzzer that executes lots of crazy stuff. Sort of Android's monkey mode. And ultimately I personally hope that we will get to the point where we will enable live collaboration in the Audiotool of course.
The last feature I implemented is the automatic transformation of arbitrary transactions to a compound transaction. You can guess what this feature actually means for the user :). In fact it is very complex and I implemented it with the STM using only a couple lines of code (of course that is just half the story ...).
If you are interested in writing your own multi user application I think this is a very nice approach since collisions do not happen very often from my experience and the optimistic concurrency in a P2P environment achieves great results in terms of overall latency and feeling. The Google Wave protocol and their operational transform is also an interesting read.
The whole point of STM is to provide atomic access to a physical block of memory that is shared between threads or processes to avoid the need for locks and the like.
I don’t want to belittle what you have created, as you have devised a way of simplifying the coordination of object states across multiple servers down to an atomic, try/ fail/ retry level. You have created a very nice transaction system that can work across multiple machines…
.. it’s clever. But it is not STM. STM has a clear simple meaning and you risk diluting its meaning here.
David.
Multiuser Audiotool (or maybe just forking style?) will be awesome. Thanks for sharing your findings!
Interesting, I’m using server-side STM as well but only for resources that can be accessed by a LOT of users (more than what one server can handle).
Most of the time, for low-concurrency resources, doing some server resource mapping or simply using a database with transaction support is enough.
David: I cannot find a definition of an STM which implies the memory has to be bound to a single computer. I also think that your wording is wrong, since you probably mean only threads and not processes.
The STM idea is about concurrency. Since in my application processes (e.g. multiple Audiotools with 1 thread so to speak) are concurring in accessing a shared memory state without using locks. The shared memory is not bound to a single machine but replicated on n machines.
I also disagree that STM has a clear and simple meaning. If you lookup certain proposals or implementations of STM you will get lots of different approaches.
With the way you define STM I cannot use Terracota and have 1 thread running on n machines (with n processes in that case) and access the same memory. I think you will agree that this more simplified example validates my case.
Mr.doob: Forking style is already possible. For instance you can open a track like http://www.audiotool.com/track/derezzed_electrified_audience_mix/0 (which is already a fork) and fork it again.
Thank you for this awesome article been doing some research on image searches
and this has been very informative.
Thanx