Transactional Actor Model

This page describes a convergence in ideas of ActorsModel and SoftwareTransactionalMemory. Together, the two form a coordination system that seems to be much greater than either of the individual parts.

TransactionalActorModel allows for fully distributed AtomicConsistentIsolatedDurable transactions, without sacrifice of ObjectCapabilityModel provided by ActorsModel, preemptable for priority operations, and with a cost proportional to the number of involved actors and the expected probability of conflict. The probability of conflict is no worse than expected for any transactional system. Further, there are mechanisms to escape or translate the transaction models, e.g. when interacting with hardware or a third party database.

Context:

SoftwareTransactionalMemory offers transactions for a shared memory process model. Its simple programmer interface, simple semantics, and composition properties make it a very attractive option for managing concurrency, especially compared to locks.

The ActorsModel is a pure asynchronous MessagePassing process model that has seen mainstream use in at least ErlangLanguage. Separate actors are inherently concurrent, but individual actors internally will receive and process only one message at a time. Unlike in CommunicatingSequentialProcesses, there is no waiting for a response after delivering a message. ActorsModel is especially well suited to modeling ServiceOrientedArchitecture and distributed processes.

While Actors do not share memory, they do share state. Individual actors may be stateful, and can update their state (and how they respond to future messages) in response to incoming messages. A group of three or more actors is subject to race-conditions based on interleaving of message orders. Forces:

ActorsModel can be difficult to coordinate. Even simple negotiations can 'go wrong' when two or more external actors are attempting to independently negotiate with an actor. A prototypical example of a race condition:

And that's just a pair of simple negotiations between two actors. It can easily become more complicated. For example, Actor B may need to negotiate with three actors U, V, W to perform a withdrawal, any of which might be similarly disrupted due to message interleaving, may require coordination from B (message sent to U might depend on responses from V, W), and might need to be reversible (response from U might require reversing an operation started with V, W).

Of course, all this coordination easily becomes overwhelming to the poor sod stuck programming the system. Effectively, the standard ActorsModel limits the programmer to only a few options for the scenario where B wants to involve U, V, W. Option 1 couples interface to implementation (harming modularity), makes code for B more complex and less reusable due to its extra responsibilities and larger vocabulary, and blocks ActorsModel from a variety of domains (ActorsModel ineffective at coordinating or interacting with services provided by 3rd parties).

Option 2, 'LetItCrash', culturally favored by ErlangLanguage, has a much better complexity profile than option 1. Fortunately, not all RaceConditions are malign, so this option does remain viable for a wide variety of operations. But ignoring the problem doesn't actually solve the problem, and the prevalence of race hazards and potential coordination failures in standard language operations may make the language unsuitable for a number of domains and products.

Option 3, adding transaction support to B, U, V, W, if done by hand, will result in a common pattern of reinventing transactions for different scenarios, will introduce extra vocabulary and state management to the actor code, and will make the actors considerably more complex. One can expect the transaction support to be inconsistent (one might later need to integrate many ad-hoc transaction protocols), 80% complete, buggy, and slow. Further, there is a hidden cost: U, V, W may preexist B, but would need their vocabulary updated by hand in response to this scenario, which means that author of B cannot practically use U, V, W unless the author of B also has the ability to modify their code, which harms the degree to which the ActorsModel can be used to coordinate the services.

A Solution

Modify the ActorsModel to support transactions directly, in a consistent manner, ActorsModel wide. Effectively, option 3 performed automatically. Approaches to integrating transactions with code, and exact semantics, discussed later.

When a message M is sent to an actor, it is automatically sent as (M,T) with transaction T. Actors may perform the normal updates, send more messages, and create actors... by default all under transaction T. They may also enter a scoped transaction T'. If a transaction T is aborted, all state updates performed in that transaction are undone. This effectively undoes message sends for (M,T) or any scoped transaction within T. hierarchical transaction... unwinding the state of every actor, undoing any messages they sent in response, destroying actors created under T, etc. in a cascade across the runtime environment. If the transaction is aborted, it is as though the messages delivered in that transaction were never sent, and it may be automatically restarted.

T may be 'nil' if one is outside of a transaction. When outside of a transaction, all message sends, updates, etc. are 'permanent'. The ActorsModel language may allow programs to explicitly 'escape' and 'integrate with' the transaction in order to support 3rd party transactional (databases, etc.) and non-transactional (progress bars, logging, building a buffer to later send to a printer or display, etc.) services.

If a transaction is committed, it folds into the higher level scoped transaction... or becomes 'permanent' if the higher scope was 'nil'.

Resulting Context

Programmers can support consistency and avoid crashes while favoring 'simple' vocabularies for their actors, which is a major improvement in per-actor complexity, and one should expect to see near the same productivity as option 2 provides, but with much greater reliability and confidence in the product. There will be much less pressure to 'anticipate' coordination requirements when writing actor vocabularies: a simple vocabulary can be used to perform complex multi-message multi-actor negotiations because the transactions will isolate actors involved in different negotiations.

Reliability should improve and proof of reliability should become more viable because programmers can usefully make more assumptions when it comes to full and partial failures and when it comes to simultaneous negotiations. Programmers effectively have option to work with a transactional 'snapshot' of the world rather than programming for an ever-changing world, thus one has the option to use simpler strategies (like 'get' and 'set') instead of passing functions and continuations around.

Expressivity boost from SoftwareTransactionalMemory: transactions have been extended to arbitrary services (as opposed to just the memory service) and even to the life-cycle of processes themselves, allowing actors to be created and registered, and coordinated in transactions without risk of interruption or some other actor jumping in and using a partially developed actor-based dataflow system. Other system entities (databases, filesystems, GUIs, printers, etc.) can easily integrate with the TransactionalActorModel and use the transactions to know when a change is to become permanent/printed/etc.

Just as the ActorsModel naturally extends to distributed programming, the TransactionalActorModel naturally supports distributed transactions.

Waits, dataflows, pub/sub, and other concurrency patterns are, just as they were before, still naturally expressed in terms of MessagePassing and waiting on messages. The TransactionalActorModel handles a final key element of actor coordination that MessagePassing alone does not readily support.

Transaction Properties

Of AtomicConsistentIsolatedDurable, TransactionalActorModel directly provides atomicity and isolation. Durability may also be achieved for persistent actors. Consistency is not well defined for ActorsModel; in one sense, this means it is 'vacuously' Consistent (since there are no declarations of integrity constraints). Regardless, full support for isolation should make any informal notion of consistency (e.g. agreement among actors) much easier to achieve: if each operation is implemented so it succeeds or fails correctly, and the system starts in a consistent state, then the system as a whole is consistent.

It might be useful to define a weak level of consistency such that uncaught exceptions in involved actors cause (or give opportunity to cause) transactions to abort. This is a dangerous choice, though, since it means that some transactions won't ever be able to commit, and it may encourage excessive use of transactions. Alternative approaches would probably include some degree of automated analysis: that messages will be understood by the recipient, etc.

TransactionalActorModel transactions are distributed and may cross services under distinct ownership boundaries without risk to security (i.e. maintaining the ObjectCapabilityModel security naturally offered by ActorsModel). Transactions also have characteristics usable in supporting other forms of security: e.g. a certificate of authority may be attached to a particular transaction, which would ensure said authority has finite extent.

Likely Performance Impacts

Transactions paid for at the usually course grain of Actor messages should result in much better performance than fine-grained SoftwareTransactionalMemory that one expects to see when applying STM to Java or C++, especially given that ActorsModel is usually synchronized on the message queue.

However, transactions are not fully bounded in their extent, and their extent is not fully controlled by the initiator of the transaction, so it is likely that transactions will often be much larger and more widespread than one might have imagined. Transactions can involve many cyclic callbacks and will impact the final state of all involved parties. Transactions that result in infinite message loops will never commit.

Potential for starvation and livelock... but not worse than you could expect from other coordination solutions that achieve the same ends.


RE: SharedMemoryModel? vs. TellDontAsk (page anchor 'ssm_vs_tda')

Doing this [implementing a SharedMemoryModel? atop the ActorsModel] violates the principle of TellDontAsk, considered overall to be really bad form. You get what you ask for, here; if your intent is to model a shared memory system, that's precisely what you'll get, with all the privileges and problems thereof. If you construct your actor system as a legitimate object-oriented environment, wherein you map one actor per one application object, then you'll nearly always avoid this situation. I can use a screwdriver as a hammer too, and in doing so I can make it work, but certainly, I'll have problems in the process. This is a clear-cut case for simply using the tool correctly.

I agree that creating a SharedMemoryModel? atop the ActorsModel is bad form (it's a didactic example to prove a point, not a recommended practice), but I'll provide two counterpoints regarding the rest of your argument: I posit that TellDontAsk is a generally negative programming discipline for both OOP and ActorsModel, and I suspect that the popularity of TellDontAsk derives of its ability to sometimes act as CodePerfume to mask various MissingFeatureSmells and other LanguageSmells.


In a pure ActorsModel, transactions would be implemented by actors (that manage persistent state and hold the temporary state of a running transactions) and message-passing protocols between actors. E.g. just like existing distributed transaction protocols, such as TwoPhaseCommit or ThreePhaseCommit?. You could write the transaction protocols as actors. They would spawn other actors to perform the unit of work within a transactional context.

In a distributed implementation of the ActorsModel, you'd need a distributed transaction protocol to implement a TransactionalActorModel anyway.

Q: What more would a TransactionalActorModel need that could not be implemented as pure actors?

A: ActorsModel is TuringComplete so there is nothing that can be implemented by some other model that also "could not be implemented as pure actors". But that line of argument will lead you straight into a TuringTarpit. Transactions can be hand-implemented with pure actors with about the same ease as hand-implementing transactions in procedural languages... which is to say: it would be invasive of everything you do, complex, inconsistent across libraries and reusable components, and highly prone to error.

That said, you can compile code written for TransactionalActorModel by applying a global transformation into standard ActorsModel with some choice of actor-managed commit protocols. Whether doing so offers any useful properties is an open question.


Notes on TransactionalActorModel:

commit is upon 'receive': actor-model transactions need to automatically initiate commit upon the first receive after starting the transaction. Initiating commit upon entering receive state allows the transaction to continue in callback messages from the same transaction. Doing so in the first receive is necessary to achieve identical isolation semantics for transactional vs. non-transactional interactions (can't have a special 'receive-in-transaction' if semantics are to be identical). Given potential for callbacks due to observers and such, it can't always be known a-priori who is going to call you back, so this issue is actually quite critical. Example situation illustrating that commit prior to receive fails:

 Failing Scenario                            Succeeding Scenario
  A starts transaction T                       A starts transaction T
  A sends message M1 to B in T                 A sends message M1 to B in T
  A commits T (A now waiting)                  A enters receive state, implicitly committing T
  B receives M1 in T                           B receives M1 in T
  B sends message M2 to A in T                 B sends M2 to A in T
  B enters receive state                       B enters receive state
  Now message (M2 in T) is in A's receive      A receives M2 in T
    queue but can't be received in T           A continues operations in T

In the succeeding scenario, A continues operations on T almost as the transaction will be aborted if A is preempted to process messages other than those from within T prior to completion of committing the transaction, but otherwise A the transaction will continue T just like any other actor involved in the transaction.

Procedural atomic{} blocks are out, but given ActorsModel compatible synchronous IPC like SendReceiveReplyEventually they can still be achieved so long as the behaviors don't reference any 'local' mutable state:
  atomic{action} 
      becomes 
  block(send newAtomicFunctorActor(action) execute)
Any affected state would need to be in an external actor, but with SendReceiveReplyEventually one could solve this generally (and enable many optimizations) by keeping all mutable state in special 'cell' actors that respond to get, set, update, query, etc. messages. Anyhow, the procedural atomic block that makes composing transactions so easy in SoftwareTransactionalMemory becomes in TransactionalActorModel a spawned atomic functor that you immediately execute and upon which you immediately wait, but doing so requires some sort of synchronous message passing (which has its own dangers).

transaction preemption & reordering: Preemption is useful as a mechanism to help achieve performance constraints (realtime or soft realtime) when interacting with services that might be utilized simultaneously at a variety of different priority levels. In order to uniformly support preemption without violating isolation and the integrity of ActorsModel, the specification of whether or not a message is to be handled in a transaction must be determined immediately, prior to any side-effects. If a side-effect occurs between receiving a message and starting a transaction, then the actor that received the message cannot be safely preempted.

 Failing Scenario                            Succeeding Scenario
   A receives message M0                       A receives message M0 atomically
   A sends message M1 to B                       so A is in new transaction T
   A starts transaction T                      A sends message M1 to B
   A receives high-priority message M2         A receives high-priority message M2
   Environment cannot preempt M0 without       Environment aborts M0 and reorders it after M2
     violating ActorsModel (due to M1)

The ability to preempt the initial message in a transaction also allows failing transactions to be placed on hold to accomplish other work, even lower priority work (if there are other messages in the queue), before retrying the message that initiated them. This allows useful strategies for backing off of transactions that result in conflicts when other work is available. Prior to considering this, one may preempt messages to any actor involved in a transaction except for its initiator, so this also offers uniformity that makes the whole TransactionalActorModel much easier to reason about (any actor involved in a transaction can be preempted).

No actual capabilities are lost in achieving this uniformity... one can still mix atomic and non-atomic behaviors by spawning off actors to handle the atomic parts (e.g. as in the atomic{} block example above). This uniformity doesn't help for actors that aren't in a transaction (which might be waiting a long time for transactions to complete), but it guarantees that all transactions are preemptable, which reduces the realtime search space to non-transactional behavior (e.g. waits on replies, timing or scheduling concerns, etc.).

While receive atomically is possible, it is not practical: it would generally be favorable to decide whether a message will be handled transactionally after seeing or somehow pattern-matching on the message. One approach would be to associate the atomic keyword with message handlers (in which case it should be associated with the implementation rather than the interface).

integration with synchronous messaging: A mechanism such as SendReceiveReply or SendReceiveReplyEventually may be used with TransactionalActorModel, with some constraints. The big constraint is that you cannot wait on a 'receive' from a later actor before replying to an earlier one - one is effectively forbidden the 'receive^n reply^n' pattern (for n >= 2), which is necessary for mechanical synchronization (semaphores, mutexes, queues) and would interfere with transactions in all but contrived circumstances. Also, for better or worse, transactions don't interfere with deadlocks that would normally occur with synchronous messaging due to cyclic waits... other mechanisms (like 'eventual reply') are needed to ameliorate the deadlock issue. Finally, a synchronous 'reply' from a transaction initiator must wait until the initiated transaction fully commits due to potential for reset.

transactions & object capability: To avoid violating the ObjectCapabilityModel inherent to ActorsModel, there is no 'global' transaction management service, at least not in distributed systems or in any semantic sense. Actors that don't have special needs are likely in practice to share a transaction manager within a trust boundary (e.g. a particular machine) for simplicity and optimization, but it is impossible in the general case to know which actors were involved in a transaction you started even after the fact.

escaping transactions & commit protocol: example purposes being to report on the status of a transaction (e.g. progress bar), to request authorizations from a user-agent that may need to contact the user (e.g. to grant access to a secured resource, process accounting pay-for-service, etc.), to integrate with third-party transaction software (e.g. databases), to integrate with systems that don't support transactions (e.g. hardware, third-party software, queue up pages for a printer), to do some optimizations (e.g. eliminate a harmless conflict when using a shared random number generator), etc. This might be performed at some level other than the actor (i.e. it could be performed at an actor-configuration level). An actor that escapes transactions needs to effectively manage all its own transactions (it can't just pick a few methods and escape those), and will need to more explicitly partake of the commit protocol. Explicit integration with the commit protocol will require the commit protocol itself be standardized ahead of time... so choose a commit protocol wisely because it will become expensive to change later!


Eliminate the Message Queue:

Actors are usually abstracted as processing one message at a given time. This assumption was a cause of two of the above restrictions: commit on receive (to avoid situation where message is waiting in message-queue that must be processed before commit), and atomic-on-receive (to support preemptable transactions, since no other message can be processed while M is being processed).

By eliminating the one-message-at-a-time restriction, the other restrictions are no longer implied. One may then perform fine-grained transactions even within a single actor... i.e. start one transaction, commit it, start another transaction, voluntarily abort it based on replies, etc. Additional benefits of being rid of the message queue: potential for deadlock is eliminated (since there are no cyclic waits), chunks of actors can be inlined just like normal OOP method calls, and a great more inherent parallelism can be exploited: read-mostly actors can be very widely distributed, much like LDAP, with the same actor on many different machines serving hundreds or thousands of users simultaneously.

Actor state must still be protected, but will now be 'serialized' by the 'isolation' property of transactions rather than being 'serialized' by a message queue. 'Non-transactional' messages will need to fit in, but that can be achieved by use of atomic updates to individual state cells, while allowing non-isolated users to see the writes of other transactions only after they commit.

With transactions, the message queue isn't needed any longer for the vast majority of its original reasons. If something like it ever does turn out to be useful, a special actor with restrictions (like no waiting on futures) to eliminate possibility of deadlock might be sufficient to serve the purpose.

While I was initially skeptical, the fewer gotchas and many potential performance advantages has me choosing to be rid of message queues. I still have synchronous message queues at the very edge of the system (interacting with hardware) but those actors cannot wait for replies, so deadlock remains eliminated.


TransactionalActorModel Example

Situation: a pseudo-typical interaction between six asynchronous 'pure' actors A, hA, B, C, D, E with the following steps (which may occur in any compatible partial-order):
  1 A starts transaction T upon receiving M0
  2 A creates actor hA to pre-process callback
  3 A sends message (M1,T) to B; message contains name hA
  4 A enters receive state, waiting on a message.
      implicitly, initializes commit of T
  5 B receives message (M1,T) from A
  6 B performs a computation, possibly involving actor D
  7 B sends message (M2,T) to hA
  8 B returns to receive state
  9 hA receives message (M2,T) from B
 10 hA delivers message (M3,T) to A
 11 hA returns to receive state
 12 A receives message (M3,T) from hA
 13 A sends message (M4,T) to C
 14 C receives message (M4,T) from A
 15 C sends message (M5,T) to E
 16 C enters receive state
 17 E receives message (M5,T) from C
 18 E updates its local data based on message M5
 19 E enters receive state
 20 All involved actors in rest state; barring 
      interference, may finalize commit of T

This is intended to represent a pseudo-typical short transaction. Numbers are for reference; events are sequenced from a partial-order; the notation (M,T) means that message was literally received with meta-data marking it as belonging to transaction T. It is worth noting that all actors that partake in a transaction must eventually end in a passive state relative to the transaction (either receive state or terminate) before the transaction is considered 'complete' and can be committed. Further, the initiator may continue to receive messages associated with the transaction after commit has been initiated, as in step 12.

(work in progress)

Case One - Everything Works! If there is no interference from other transactions that ends up overriding the behaviors of this one, then everything has worked. Once the transaction commits, the final 'receive' states of the involved actors becomes 'permanent'. In case of 'pure' actors that don't update their ow If not explicitly marked as single-use or some such, hA will likely be garbage-collected at some point in the indefinite future.

Case Two - A receives message N0 from outside transaction at step 4 At this point the scheduler (or some other system service outside A) has the option of pushing A to process another event, possibly even starting another transaction. The scheduler could usefully make such a decision based on properties ascribed by programmers (e.g. marking a particular message handler implementation as asynch if one doesn't expect problems). Usefully, parallel processing of two transactions will rarely conflict unless both lead to update of the same stateful actors, so systems that act like switches can be made very heavily parallel. The scheduler also has the option of delaying N0 until giving the transaction from M0 reasonable chance to complete its commit; so long as N0 isn't delayed indefinitely, ActorsModel semantics remain supported. The scheduler can vary its decision on an actor-by-actor basis in order to maximize parallelism where conflict is unlikely and reduce it where conflict is likely.

Case Three - E aborts transaction Due to conflict, the transaction involving the update to E is rejected. At this point, depending on the transaction protocol, E will reply with abort when or before requested to pre-commit. This decision is relayed back to C. C would have asked due to receiving a commit request from A, and will so tell A to abort and undo its own changes. A will then tell B to abort, and will tell the system that hA (which was created in the transaction) can be destroyed. At least, this is semantically how transactions are aborted.

In practice, many or most actors involved in any given transaction will be in the same local machine or system and thus the actual communications can be trimmed down and processing optimized to an enormous degree. In particular, if a particular machine controls actors A, B, C, hA, and E, then that machine can simply use global version numbers and such in each transaction and verify them all at once. Further, if a particular machine knows that outgoing communications for a particular transaction went to D on another machine, then it can fire off a message to D asking for its pre-commit status right away even before it starts computing conflicts for A, B, C, hA, and E.

Case Four - C receives another message N0 after entering receive state in step 17 Same as Case One, except in C. The fact that C is not the initiator of the transaction doesn't change a thing. Parallelism may be achieved if conflict is unlikely whether or not N0 is in a transaction.

Case Five - C is involved in another transaction prior to receiving message in step 15 Same as Case One and Four, except from the other side.

Case Six - D gets involved, does unknown stuff in step 6 Well, at this point there are many possible things that weren't named that D could do. D could never terminate, in which case the whole transaction could be left hanging while waiting for D to commit... then eventually be killed and retried later because the scheduler decides that waiting takes too long and ends up processing a conflicting transaction. Livelock doesn't disappear in TransactionalActorModel (nor does deadlock if you introduce synchronous communication!). If D throws an uncaught exception, that will be up to other policy issues... i.e. a failure handler might receive the failure in that transaction and choose to abort the transaction or simply to transactionally log a failure.


Deadlock and Livelock and Failure Semantics

TransactionalActorModel, while offering considerable simplicity in making actions that would be successful in isolation also successful in concurrent environments (resisting race conditions), does very little to reduce need for failure semantics when it comes to interactions that would be 'doomed' even in isolation. It, as written, merely ensures such interactions fail atomically and do not fail to concurrent interference.

With transactions, livelock and deadlock can occur based on choice between optimistic and pessimistic resource management and decisions on how to go about recognizing and resolving conflicts. Progress in the face of transaction-based deadlock can be guaranteed in the sense that, if two transactions are competing to commit, policies can easily be negotiated (possibly after a few optimistic retries) that ensure only one of them will be aborted.

In ActorsModel, livelock, forever-cycles, and (if synchronous messaging is added) even deadlock can occur even in complete isolation. Programmers can mess up on multi-message protocols, can leave continuations hanging on remote processes that forget to reply, etc. Predicting, avoiding, detecting, and handling these problems, which would occur even in isolation, will require a set of utilities almost completely orthogonal to TransactionalActorModel.

Failure and Explicit Abort (with SendReceiveReply)

If a transaction seems to 'fail' such that the initiator wishes to undo the transaction and try something else, that's a different sort of beast than is transaction failure due to concurrency conflict. I believe (but cannot prove) that such a decision should be limited to the initiator of the transaction. Doing so allows most actors to be written transparently to the transaction model - i.e. only the actors that initiate the transaction are explicitly aware they are in one, and even they don't know whether they're party to a hierarchical transaction or not.

It's worth noting that such a capability isn't useful in pure ActorsModel. The basic reason: in pure ActorsModel, it is impossible to get feedback as to how the transaction is going, and thus it is impossible to make an intelligent decision for whether or not to abort. But, with SendReceiveReply (or SendReceiveReplyEventually), one can wait on replies from other actors. This would serve as feedback to make an intelligent decision to abort.

So, suppose initiators of transactions are given opportunity to explicitly abort in an ActorsModel modified for SendReceiveReply. This would allow, for example, the initiator of the transaction to decide it didn't go well and to undo a behavior. This is a major boon to achieving Consistency (from AtomicConsistentIsolatedDurable). With judicious application and libraries designed to leverage it, you really can have a world where (nearly) all observable behaviors succeed... a virtual PleasantVille.

The question, though, is what to do on abort. What's next? Well, I'll propose: the input to explicitly abort can be another message handler, which will be processed later, potentially with its own transaction properties. This retry doesn't need to occur immediately; it may occur at some arbitrary time in the future, thus allowing other messages to be processed in the meanwhile (if the actor has a queue of such messages). Anyhow, it would be silly to retry the exact same behavior that just failed in an atomic and isolated manner, and it would hurt a variety of other ActorsModel properties to hold that message indefinitely while waiting on a change in the environment. A new message handler can be abstracted and informed by the prior failures.

Usefully, this achieves a feature I had been looking for from Transactions: the ability to perform something like 'behavioral search' patterns where behaviors are tried and cleanly aborted until the desired effect is observed. Unlike a pure logic search, behavioral search can be performed with a very limited model of the environment, but it is usually difficult to achieve in a safe manner because there is no standard way to reverse behaviors that happen to be reversible. Use of transactions with SendReceiveReply and explicit abort allows behavioral search to push right up to the limitations of reversible behaviors that can be observed as replies. It won't help for moving actuators around or firing weapons, but it may help a great deal for trying multiple negotiation-options between services or performing a protocol handshake. (related: FirstClassUndo)


Speculation on Performance Cost of Transactions

TransactionalActorModel has not been implemented yet, but there's no fundamental reason to expect it to do much better or much worse than SoftwareTransactionalMemory in terms of performance. Due to supporting object capability model there is potentially a good bit of latency during a commit, but the management itself is simplified.

Programmers who have access to facilities like SoftwareTransactionalMemory and TransactionalActorModel will need to be taught to avoid abusing them - i.e. the sort of "I made it atomic just in case" statements. Livelock is a risk if transactions are overused. Fortunately, the risk is mostly to their own transactions (as opposed to locking up everyone else's code), and global progress can usually be achieved by applying some heuristic coordination to retried transactions that have conflicted before. (Also, in an event of an aborted transaction, an actor with many messages on its queue can consider trying to process some of those other messages prior to returning to the one that was aborted... ActorsModel doesn't guarantee arrival order.)


"Decaying" Transactions (with SendReceiveReply)

Basic idea: A handler second option offering a weaker form of 'atomic decay' which, unlike normal 'atomic' handlers, will guarantee transactional properties only up through replies.

This only works for ActorsModel modified by use of SendReceiveReply (or SendReceiveReplyEventually with the ability to wait on reply). It is incompatible with 'pure' ActorsModel, which offers no means to distinguish sends from replies. It is also incompatible if one cannot wait on replies in the handler (i.e. it would be incompatible with EeLanguage's "far" reference messaging).

These 'decaying' transactions are potentially weaker than the normal sort, but are far more resistant to overuse and are still sufficiently strong for what I'd guess to be 95% of all transactional work. For example, they still are at least as strong as SoftwareTransactionalMemory, and at least as strong as transactions common to databases and distributed hashtables. (Those transactions are usually limited to read/write behaviors, as opposed to the quite arbitrary behaviors accessible to TransactionalActorModel.) Beyond those capabilities, the 'decaying' transaction is still good enough to atomically negotiate an agreement between two or more independent services or protocols, but then allows the performance of said agreement to naturally decay back into non-transactional behavior. Normal transactions can do the same (by breaking down negotiation and performance into two phases through a state-based intermediary), but it isn't nearly so convenient.

This weakening is based on the concept of "activity". In the ActorModel, an "activity" is defined as the set of messages leading to a reply to an initial message. If I send a message and either don't expect or plan to drop the reply, then that message isn't part of any activity, but it might initiate new activities. Activities can be tracked by attaching identifiers to them (short random numbers are good enough), and zeroing the number whenever a message is sent for which the reply is dropped. In ActorsModel with SendReceiveReply, 'activity' identifiers are available at no extra cost because one will use them anyway to efficiently and securely detect distributed deadlock.

The regular transactions described in the above sections might cross multiple activities (and, indeed, might never terminate). This is because every 'new' activity introduced by the full 'atomic' transaction is still part of that transaction. For example, if you transactionally update a cell to which other actors are subscribed, that cell will call back to the subscribers to tell them of the update. Those callbacks would also be transactional. That can lead to some useful properties, such as being able to undo the cascading effects of a change, but also leads to high-risk transactions that are likely to be aborted.

The basic idea for decaying transactions is to allow messages that don't contribute to the reply to fall out of the transaction. This makes the 'activity' a transaction, but allows the side-effects and ongoing behaviors from the activity to become non-transactional, at least once the 'transactional' portion commits. If the decaying transaction aborts, then it must still abort atomically as though it never happened.

Fundamentally, this is implemented by having the runtime delay outgoing messages from the transaction until it believes they are required for the initiator to complete the message handler and eventually reply. Once the initiator of the decaying transaction has replied, all other outgoing messages may simply become non-transactional and be sent normally. If the initiator of the decaying transaction aborts the transaction, or if there is a conflict, the delayed messages are simply dropped. That said, it's perfectly okay for the runtime to be imperfect and to treat some messages as part of the transaction even if they do not contribute to the reply! The runtime or optimizer is free to make an intelligent trade-offs between minimizing delays and minimizing risk of abort.

If explicit abort is supported, then for 'atomic decay' transactions, one would only need to verify that the 'abort' happens before the 'reply' behavior in the handler definition.

Variation: allow one to intentionally introduce 'transaction barriers' across which transactions from different systems begin decaying. Useful for performance control (since you can guarantee sends without replies can be implemented non-transactionally), and for reducing the influence or extent of transactions out of fundamentally non-transactional systems. Normally, a transaction barrier could be implemented by having the transaction 'finish' with setting some state, then having another system read (poll) that state. So, this makes it easier to create transaction barriers, and offers better performance than polling. OTOH, it also makes easy to undermine the use of transactions as the basis for an observe-and-undo logic system (as do transaction barriers and polling-based behavior in general).


See: ActorsModel, SoftwareTransactionalMemory, SendReceiveReplyEventually, Transactions for ProcessCalculus (http://lambda-the-ultimate.org/node/1813), FirstClassUndo

CategoryConcurrency

EditText of this page (last edited August 30, 2012) or FindPage with title or text search