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.
Now having a real graph is fun and I was not surprised that lots of people invested their brainpower in graph algorithms. For the desktop in the AudioTool I always wanted to implement some kind of automatic layout algorithm. My first idea was to build a spring between two editors connected by a cable. I thought that this could be too complex but after spending the last days with graphs this became a possible solution and there are already algorithms which do the same thing: build springs for connections and let the system solve itself. I did some tests in a sandbox already but hopefully I can implement this in the AudioTool before FITC Amsterdam. The graph you see in the picture is a result of the graph layout engine.
Anyways, what if you think about the dependencies in your layout engine as a graph structure? You have usually three cases when calculating a size: relative known size to “some kind of available size”, absolute known size, absolute unknown size. Those cases can be reduced to their most simple form on a piece of paper and a graph structure evolves. You can get rid of observers and listeners in such a system if a connection in the graph has the meaning of invoking the layout engine again on a subset of nodes. Those subsets could be optimized even more if you figure out the strongly connected components in the graph. I have to admit that I did not implement this system yet but it makes a lot of sense in theory currently… something which makes working on a layout engine interesting again ;)
