Application state and transactions

Transaction is an atomic transition from one valid state to another. That means whether that transition succeeds of fails every access to the application state will be consistent. However, because of the way computers work, application state cannot be changed in its entirety momentarily and the changes have to happen sequentially.

An example: assume we have a UI frame with controls in it. At first the frame size and controls positions are consistent, but if the frame is resized the controls have to be laid out according to their resized parent. Their sizes and positions are adjusted one by one and when that’s done everything is consistent again.

If we were to consider the whole application state during that process — it was inconsistent, however when it was done, consistency was restored. Why did it work out? The reason for that is that during that process the change was propagating by updating parts of the state that were out of date using data that was already up to date. That is, control layout was calculated using parent size. But if the layout algorithm were to use sibling size for that calculation — that size could be out of date which would lead to overall inconsistent layout. To get consistency we need state changes to propagate in such a way that the bits change in order of dependency.

In other words consistency should be considered only in terms of data being accessed. The entire state can’t change instantaneously but the whole of it cannot be accessed at once either, so we should only concern ourselves with making sure that state is consistent as it is being accessed.

Approaches to state consistency

Understanding this leads to a number of ways of ensuring state integrity. One is having some basis dataset with all of the rest of application data derived from it on access, being a “view” on that dataset. This works well for applications where the basis is small or structurally simple so that changes to that basis itself can be ensured to be transactional. This is essentially the approach database driven applications take and the reason for normalizing the schemas. (BTW, consider how materialized views are actually event-driven).

Another way to get consistency is to design the application so that the dependency order is clearly defined (which isn’t provable most of the time). An example of this approach would be window layout described above: when the parent size changes, layout the children recursively. This is probably the most common approach to state consistency but unfortunately it’s very hard to scale, which is one of the primary reasons why developing big applications is so hard and produces so many bugs.

Reaction and similar systems solve this issue in a different way, which we’ll examine later.

Functional programming, thread-safety and more

Also, I’d like to point out that state consistency is the subject of thread-safety and functional programming as well. Pure functional programming makes all of the state local, eliminating the issue altogether, but that comes with a cost. And thread-safety is a concern for consistency of any state shared between threads. When code in one thread modifies the state it might be accessing the data in such a way that the change propagates sequentially and all its reads are consistent. The same is extremely hard to guarantee in presence of other threads that can access the same state at any time. That’s why the solution is to synchronize reads and writes of the same data between threads with locks or by other means — that ensures that if the change is transactional (i.e. preserves consistency) then it will also appear that way to other threads as long as they are synchronized. This is called pessimistic concurrency.

Also consider how message-passing systems and actor model (Erlang) are also ways to solve the very same problem in various contexts by redefining what the consistent state is. With message-passing we consider the state “message pending” a consistent state. This way the transition from “have incoming message” to “have outgoing message” can be viewed as transactional and for that reason the state changes to consider are smaller and are much easier to guarantee to be consistent. However it does not solve the case when there are multiple incoming changes that have to processed together. We’ll look at these cases later.

Concurrent transactions and the need for rollback

Let’s look at how and when we expect errors to be signaled in code we write. Usually if the call returns it means that the operation succeeded — it would be extremely hard to write code in a language where exceptions related to some past operation would be thrown at some later time. In distributed and other parallel systems this requires each nonlocal operation to be synchronized which quickly becomes unfeasible. One way to work around it is to make as many operations local as possible, which is something that allows pure functional languages to be able to utilize multicore CPUs more immediately, without changes to the code as the operations are already local. Sometimes that cannot be done, for ex. in case of databases — if there are multiple concurrent updates to the same table, there’s no way to guarantee they will not intersect but executing them sequentially is not acceptable for latency reasons.

Solution to this is to allow transactions to fail. This breaks the expectation of every operation succeeding or failing immediately, deferring it until the end of transaction, but it allows multiple transactions to execute in parallel. Now, what would a transaction failure imply? If we had three concurrent transactions where two were completely independent (TA, TB) and a third (TC) ended up stepping on others’ toes (we’ll look into what that could mean later), the last transaction would fail and to fulfill the requirement of atomicity the state of the system would have to be valid which means that changes from TA and TB would be incorporated but none of the TC changes would. This is called optimistic concurrency.

So, basically, if we can integrate changes made by transactions, they succeed, and if not, at least some of them fail. How could we integrate the changes and how can we tell if the result will be valid? (Given that each of the changes on its own is valid, which is application’s concern). First of all we need the changes of each transaction to happen in isolation, so that we can selectively drop some but not all of them. Second, we need the application to do all the relevant reads inside the transaction, i.e. if the write depends on some state data, that data should be read inside the same transaction. Third, we need to record with some granularity what reads and what writes each transaction makes.

Knowing exactly what data was read during some transaction (TA) we can check if any other transaction (TB) that was committed while the TA was running and if that transaction changed the data TA used. If TA depends on data that has changed since (by TB) — obviously it has to fail, because the changes it made cannot be incorporated anymore.

For example imagine two transactions running in a banking system:

1. TA reads current balance and other info about some user to update his credit rating that it proceeds to store somewhere else in the database
2. TB reads current balance and decreases it by some amount and debits the difference to some other user’s account

Let’s assume both started simultaneously.

• In one case TA will commit first — as TB did not commit yet, the balance TA read is unchanged and it succeeds. When the time comes for TB to commit as well, it succeeds too, as TA didn’t change the balance at all.

• Another case, where TB commits first, it succeeds too as there are no other changes to the balance. But TA does not, as the balance was changed by TB in the meantime. The credit rating update is not written out and is never visible to any other transactions.

One can think of these transactions as functions mapping some specific subset of state — input, to some other, possibly intersecting, subset of state — output. The output is never used if the input became out of date during the processing and results in a rollback.

You should have noticed that this approach requires precise knowledge of other transactions’ status which means that commits themselves have to be synchronous, but this is necessary because we want to know for sure if the transaction is successful at commit time, not defer that result even more.

There’s a way to get even more concurrency between transactions for some use cases. To do that one would need to introduce rules to merge multiple states even if they contain intersecting changes from their shared “parent” original state (which might be not the one immediately previous to respective transactions). This approach is called eventual consistency and rarely can be used for anything other than small subset of entire application behavior. However this allows concurrent transactions to run completely independently, even if the connectivity issues partition the system.

It’s interesting to see how Google BigTable doesn’t allow transactions across tablets, but still has the capability of transactional integrity for predefined groups of rows (entity groups). This allows the commits to be serialized for such sets of rows but still be completely independent between these sets.

Transactions in Reaction

Right now Reaction can only handle sequential transactions, but the benefits it brings to them would certainly be welcome in distributed systems as well. I’d like to work on that, but it’s unlikely to happen very soon. Lets look at those benefits anyway.

The major problem with state consistency is complexity of that requirement. The bigger the application the more complex a set of rules defining the validity of state. It’s complicated further by that fact that those rules depend on each other and there’s no guarantee they do not conflict. Usually it’s up to the programmer to lay these rules out in sequence and to convince themselves the order is actually correct in all cases and there are no rule conflicts. Systems implementing the transactions themselves (be it database server or something else) cannot check if the changes supplied to them by the applications are valid, the most they can guarantee is that those changes will be applied “at once” as far as other clients concerned and that the writes don’t conflict among transactions (if concurrency is supported). There’s no way to detect at this level if any of the supplied changes were invalid, such as one write masking another within the transaction.

The way to deal with complexity is to break system down into smaller parts. And as we still care about consistency just as much as before, we need to make sure that given correct behavior of these smaller parts we can imply that their aggregate is correct as well. As it turns out we can approach this task much in the same way we would approach concurrent transactions: we can ensure integrity of changes across rules by tracking their reads and writes and making sure that all reads accessed valid data. That is if some rule changes something that was read by another rule, the latter needs to be marked invalid and rolled back along with any rules that used its output. This does not imply that the entire transaction will immediately fail however, as we have the opportunity to evaluate the rules again, in different order.

Another benefit of such per-rule read/write tracking is that it enables us to detect rule circularity and conflicts, something that would manifest as bizarre and elusive bug in a different system, with Reaction results in immediate and relatively easy to understand error.

Before we go into details of the requirements for the rules in Reaction let’s look at the terminology.

• Cells are containers for the values that define the application state. Reads and writes are tracked at cell granularity.
• Rules define how values of some cells can be derived from others.

Each rule is bound to a cell and can define value of that cell or even set values of multiple cells. The rule are implemented as regular Python functions or methods and their reads and writes are tracked by cooperation of the cells they access — the reads and writes are reported to the transaction controller which then remembers the dependencies between cells, detects conflicts etc.

There are two aspects to what a cell does:

• Subject — when a cell value changes (due to its rule evaluation or if set by some other cell rule) its listeners are notified.
• Listener — a cell rule gets re-evaluated when any of its subjects change

So whenever a cell rule is evaluated, every cell it reads becomes its subject and it becomes their listener. Note that previous subjects are disconnected unless they were read again. Also, references to subjects are kept as usual, while references to listeners are weak. This has two important implications:

1. The cells can get added and drop out of the listeners “network”. In other words the application state size and the number of rules can change at runtime.
2. The rule dependencies are dynamic as well and require zero management or declaration.

The latter also implies that order in which the rules should be evaluated cannot be known beforehand. So initially they run essentially in random order, but as their dependencies and effects are recorded they get rearranged in consistent order if possible. It should be noted that as rules get added and removed the order of evaluation will change to make sure it is valid at all times.

All of this is possible because the consistency requirement is split into interdependent rules and there are certain restrictions on those rules.

This article was never finished.