Difference between revisions of "Transactions"

m (Newlines.)
 
(10 intermediate revisions by 2 users not shown)
Line 1: Line 1:
This is something I've been looking at for the last day or so.  I was really looking for a concurrency solution that solves issues of concurrency from a language standpoint and it seems like SCOOP is currently at a standstill research-wise.
+
[[Category:ECMA]]
  
I'm not an Eiffel compiler writer so I don't know exactly how every piece can be implemented but it seems doable.  The proposal relies on transactional memory, probably implemented as software transactional memory right now.
 
 
If this proposal is feasible and desirable, it would need to be formalized by someone (not me) in to some language rules.
 
 
I'm crossing my fingers for a language solution to concurrency!
 
 
--------------------------------------------------
 
 
A proposal for transaction based concurrency in Eiffel by Colin LeMahieu,
 
A proposal for transaction based concurrency in Eiffel by Colin LeMahieu,
  
 
Rationale:
 
Rationale:
The un-computability of determining if a program based on locks will deadlock in general necessitates using alternative forms of concurrency.
+
The intractability of determining if a program based on locks will deadlock in general necessitates using alternative forms of concurrency.
  
 
Abstract:
 
Abstract:
Line 18: Line 11:
 
Behavior:
 
Behavior:
 
*A feature can be a transaction
 
*A feature can be a transaction
*All feature calls are asynchronous
 
 
*Transactional features guarantee atomicity and isolation across the execution of the feature
 
*Transactional features guarantee atomicity and isolation across the execution of the feature
 
*When a transactional feature calls another transactional feature, the transactions are composed.
 
*When a transactional feature calls another transactional feature, the transactions are composed.
*The compiler and runtime determine the scheduling either through compiler analysis, runtime statistics, or runtime transactions.
 
 
*When a transactional feature is aborted it is automatically retried until it is not aborted.
 
*When a transactional feature is aborted it is automatically retried until it is not aborted.
 
*External features without abort and commit semantics are executed when all transactions have been committed or aborted and executed serially with respect to the system, this is ensured by the runtime.
 
*External features without abort and commit semantics are executed when all transactions have been committed or aborted and executed serially with respect to the system, this is ensured by the runtime.
Line 28: Line 19:
 
Use the 'transaction' keyword to define a feature as a transaction
 
Use the 'transaction' keyword to define a feature as a transaction
  
feature<br/>
+
<e>
obligatory_transfer_example(account, amount) is<br/>
+
feature
transaction<br/>
+
withdraw(account, amount)<br/>
+
deposit(account, amount)<br/>
+
end<br/>
+
  
withdraw(account, amount: INTEGER) is<br/>
+
  obligatory_transfer_example(account, amount) is
transaction<br/>
+
    transaction
account.balance.withdraw(amount)<br/>
+
      withdraw(account, amount)
end<br/>
+
      deposit(account, amount)
 +
    end
  
deposit(account, amount: INTEGER) is<br/>
+
  withdraw(account, amount: INTEGER) is
transaction<br/>
+
    transaction
account.balance.deposit(amount)<br/>
+
      account.balance.withdraw(amount)
end<br/>
+
    end
 +
 
 +
  deposit(account, amount: INTEGER) is
 +
    transaction
 +
      account.balance.deposit(amount)
 +
    end
 +
</e>
  
 
Use the 'external', 'abort', and 'commit' keywords to define a transactional external feature. 'External' defines the external transaction functionality.  'Abort' defines functionality to roll back any state changed in 'external'.  'commit' defines functionality to commit the transaction of 'external'.
 
Use the 'external', 'abort', and 'commit' keywords to define a transactional external feature. 'External' defines the external transaction functionality.  'Abort' defines functionality to roll back any state changed in 'external'.  'commit' defines functionality to commit the transaction of 'external'.
  
feature external_feat is<br/>
+
<e>
external<br/>
+
feature
""<br/>
+
 
abort<br/>
+
  external_feat is
""<br/>
+
    external
commit<br/>
+
      ""
""<br/>
+
    abort
end<br/>
+
      ""
 +
    commit
 +
      ""
 +
    end
 +
</e>
  
 
Design by contract:
 
Design by contract:
 
*Preconditions and postconditions retain ECMA semantics.
 
*Preconditions and postconditions retain ECMA semantics.
*Features with preconditions and postconditions can only be called from a feature that is a transaction as a validation constraint.
+
*Example: If a transactional feature 'f' wants to call feature 'g' with a precondition 'a', 'f' can check 'a' before calling 'g' and is assured that 'a' will be the same once 'g' is being executed by the transactional nature of 'f'; 'a' will either remain valid or 'f' will be aborted and retried.
*If a transactional feature 'f' wants to call feature 'g' with a precondition 'a', 'f' can check 'a' before calling 'g' and is assured that 'a' will be the same once 'g' is being executed by the transactional nature of 'f'; 'a' will either remain valid or 'f' will be aborted and retried.
+
*Precondition wait semantics as introduced with SCOOP do not need to be used.
*Postcondition wait semantics as introduced with SCOOP do not need to be used as the compiler or runtime will determine the execution schedule of a program.
+
 
*Class invariants determine the consistency of transactions and are checked every time a transaction is committed and after it is aborted
 
*Class invariants determine the consistency of transactions and are checked every time a transaction is committed and after it is aborted
  
 
Deferred features:
 
Deferred features:
*Deferred features can be redefined to be either a transaction or not.  If the feature must be transactional, the designer should encapsulate the call to the deferred feature within a transaction feature.
+
*Deferred features can be redefined to be either a transaction or not.  As long as the feature satisfies its contract, the detail of whether the called feature is implemented as a transaction doesn't matter.
  
 
Agents:
 
Agents:
 
*Agent semantics will not change.
 
*Agent semantics will not change.
  
Exceptions:
+
Mutexes:
*The feature {ANY}.last_exception is obsolete
+
*Code using mutexes will continue to work, however they should be replaced with transactional code as soon as possible to avoid the possibility of deadlocks associated with locking.
*The ANY class contains a new feature last_exceptions and is a collection of exception objects that have been thrown within the context of the current feature.
+
*All features within a feature must be executed and either succeed or generate an exception before the enclosing feature can move to the retry clause or propagate an exception.
+
*If a feature doesn't handle all exceptions, its transaction is failed(aborted and not retried) with an exception of type ROUTINE_FAILURE
+
*When a lower priority feature has a transactional dependency on a higher priority feature that fails, it will fail with an exception of type TRANSACTION_FAILURE which is a subtype of ROUTINE_FAILURE
+
  
Priority:
+
Notes:
*If two calls, 'g' and 'h' within a feature 'f' are in conflict, priority is assigned by order of program text and the feature appearing later in the program text will be aborted and retried.
+
*Unlike database transactions, durability is not guaranteed with feature transactions, memory is inherently volatile in the face of system errors.
*If a looping construct is in conflict with earlier iterations of its loop, priority is assigned to earlier iterations of the loop and later iterations will be aborted.
+
*If a recursive call is in conflict with itself, priority is assigned to the top level nesting and the deeper nesting calls will be aborted.
+
  
Thread library:
+
*It's impossible for a transactional feature to reliably act on a legacy external featureDuring the execution of a transactional feature, any of the actions may be aborted and retried and since legacy external features cannot be aborted, there is no reliable way to undo that action.
*The thread library is obsoleteAll classes should be marked obsolete.
+
  
Threads:
+
*It might be better to use a keyword to define a feature as non-transactional instead of using a keyword to define a feature as transactional.
*Explicitly creating threads is redundant.
+
*Legacy external features that create threads must block until the threads are complete.  Code inheriting from THREAD in the EiffelBase threading library and effecting execute will continue to work simply by using new feature call semantics; the library will need to be changed to allow the new runtime to schedule the feature's execution.
+
  
Mutexes:
+
== Examples ==
*Code using mutexes will continue to work, however they should be replaced with transactional code as soon as possible to avoid the possibility of deadlocks associated with locking.
+
Transactions are assured with transactional memory, probably implemented as software transactional memory.
 +
----------------
 +
Example of transaction:
  
Legacy:
+
<e>
*This language change is fully backward compatible with serial code, however, performance benefits would only be seen when using code that does not reference external features that don't have transaction semantics.
+
feature
  
*Building transactions over code that references legacy externals can cause runtime routine failures; the overlying solution would be to eliminate legacy external features.
+
  correct_removal(container: DISPENSER) is
 +
    transaction
 +
        -- This is a transaction so it is assured to be atomic and isolated
 +
      if
 +
        not(container.is_empty)
 +
      then
 +
        container.remove
 +
      end
 +
    end
 +
</e>
  
*If a legacy external feature is executed within the context of a transaction, the routine is not run and generates an exception of type EXTERNAL_ROUTINE_FAILURE which is a subtype of ROUTINE_FAILURE.
+
This feature is assured to be correct because is is isolated and atomic with respect to the system.  If the container has been modified between the call to is_empty and remove, the feature would be aborted and retried.
 +
-----------------
  
*External clauses without abort and commit clauses are called 'legacy externals' and are marked as obsolete by compilers supporting legacy externals.
+
<e>
 +
feature
  
*Systems that allow legacy external features, without abort and commit clauses, cannot be executed within transactions.  The compiler could detect many of these through system analysis however the runtime will need to make explicit checks against legacy external calls to make sure they do not exist within the context of a transaction for things such as agents or inheritance substitution where a feature is redefined to be implemented by a legacy external.
+
  incorrect_removal(container: DISPENSER) is
 +
    do
 +
      if
 +
        not(container.is_empty)
 +
      then
 +
        container.remove
 +
      end
 +
    end
 +
</e>
  
*Legacy external features are executed by stalling transaction execution, making sure all transactions have committed or aborted, making sure nothing else is executing in the system, and running the legacy external.
+
This is the standard example of concurrency issues with preconditions.  The container can change between the call to is_empty and remove. Using transactions avoids this.
 +
---------------
 +
Legacy externals example
  
*We're essentially forcing legacy external features to be transactions by making sure no other transactions are currently in progress and there is nothing executing in the system.
+
<e>
 +
feature
  
Notes:
+
  use_legacy_external(item: LEGACY_ITEM) is
*Things that are seemingly serial, such as writing text to the screen in a certain order, are actually dependency relationships; specifically appending to the screen.  If there are 2 calls writing to the screen, the second call depends on the result of the first call and the compiler or runtime will either optimize this and have the second call wait, or the second call will abort at runtime until the first call completesThese two could actually run in parallel in the case where the first call writes nothing to the screen.
+
    do
 +
      print_item(item)
 +
      log_item(item)
 +
      -- At this point the runtime will block until print_item and  
 +
      -- log_item have both committed, it will ensure nothing is running
 +
      -- in the system and then run the external item serially.   
 +
      -- This is the non-concurrent way to ensure something executes as
 +
      -- a transaction, isolated and atomic.
 +
      use_item(item)
 +
    end
 +
 
 +
  use_item(item: LEGACY_ITEM) is
 +
    external
 +
      "..."
 +
    end
 +
 
 +
  print_item(item: LEGACY_ITEM) is
 +
    do
 +
      ...
 +
    end
 +
 
 +
  log_item(item: LEGACY_ITEM) is
 +
    do
 +
      ...
 +
    end
 +
</e>
  
*Unlike database transactions, durability is not guaranteed with feature transactions, memory is inherently volatile in the face of system errors.
+
--------------
 +
Example of need for runtime checks on agents in systems that allow legacy external features.
  
*It's impossible for a transactional feature to reliably act on a legacy external feature.  During the execution of a transactional feature, any of the actions may be aborted and retried and since legacy external features cannot be aborted, there is no reliable way to undo that action.
+
<e>
  
*The asynchronous semantics of feature calls gives the interesting effect of the programmer not being aware of the order in which feature calls are executed. This allows the compiler or runtime to determine the serialization schedule of the program and allows for a level of parallelism not easily thought of by a human.
+
class A
 +
feature
 +
  other: B
 +
  legacy_external_feature is
 +
    external
 +
      "..."
 +
    end
  
*Previous work focused on an idea called 'compensation' which has no real foundation in transactions.  Things that are not transactional as currently implemented such as writing files, sending network data, etc, will need classes encapsulating a transaction around that write or send.  This may be a type of journaling at the file access or network layer.
+
  call_transaction_with_agent is
 +
    --This feature would compile since it would be undecidible if 'other' is attached to an instance of C at runtime
 +
    do
 +
      other.redefined_call(agent legacy_external_feature)
 +
    end
  
*A feature that encounters exceptions tries to execute all code paths in order to gain a consistent view of the exceptions caused.  If this wasn't done, the exception reported as causing the routine to fail might vary depending on the execution plan.
+
  a_transaction is
 +
    --This feature is a compile time error as a validity constraint
 +
    transaction
 +
      legacy_external_feature
 +
    end
  
*Executing all code paths to collect all exceptions might be too restrictive for things such as the main loop of a program.  It might not be beneficial to make this change.
+
end
  
*It might be better to use a keyword to define a feature as non-transactional instead of using a keyword to define a feature as transactional.
+
deferred class B
 +
feature
 +
  redefined_call(the_agent: PROCEDURE[TUPLE[]]) is
 +
    --A reason to allow deferred features to be redefined
 +
    --to a transaction or not is for syntax simplicity
 +
    --and because the only time it matters is when building
 +
    --new transactions on top of legacy code
 +
    deferred
 +
    end
 +
end
 +
 
 +
class C
 +
inherit B
 +
feature
 +
  redefined_call(the_agent: PROCEDURE[TUPLE[]]) is
 +
    transaction
 +
      io.put_string("Line 1")
 +
     
 +
      --This call is a runtime exception.  The probability of this happening
 +
      --is low because people building transactional code should be looking
 +
      --at replacing legacy external features with transactional externals
 +
      --or some other transaction abstraction over externals
 +
      the_agent.call
 +
     
 +
      io.put_string("Line 2")
 +
</e>

Latest revision as of 07:40, 17 July 2007


A proposal for transaction based concurrency in Eiffel by Colin LeMahieu,

Rationale: The intractability of determining if a program based on locks will deadlock in general necessitates using alternative forms of concurrency.

Abstract: The Eiffel language already supports the basic idea of transactions in features. A feature either completes in its entirety or an exception is raised. The only shortfall of the current implementation is that any side effects made before the feature completes are not aborted in the transactional sense. If we adapt the semantics of a feature to include the idea of a transactional feature, we will be able to implement concurrency through transactions in the Eiffel language cleanly.

Behavior:

  • A feature can be a transaction
  • Transactional features guarantee atomicity and isolation across the execution of the feature
  • When a transactional feature calls another transactional feature, the transactions are composed.
  • When a transactional feature is aborted it is automatically retried until it is not aborted.
  • External features without abort and commit semantics are executed when all transactions have been committed or aborted and executed serially with respect to the system, this is ensured by the runtime.

Syntax: Use the 'transaction' keyword to define a feature as a transaction

feature
 
  obligatory_transfer_example(account, amount) is
    transaction
      withdraw(account, amount)
      deposit(account, amount)
    end
 
  withdraw(account, amount: INTEGER) is
    transaction
      account.balance.withdraw(amount)
    end
 
  deposit(account, amount: INTEGER) is
    transaction
      account.balance.deposit(amount)
    end

Use the 'external', 'abort', and 'commit' keywords to define a transactional external feature. 'External' defines the external transaction functionality. 'Abort' defines functionality to roll back any state changed in 'external'. 'commit' defines functionality to commit the transaction of 'external'.

feature
 
  external_feat is
    external
      ""
    abort
      ""
    commit
      ""
    end

Design by contract:

  • Preconditions and postconditions retain ECMA semantics.
  • Example: If a transactional feature 'f' wants to call feature 'g' with a precondition 'a', 'f' can check 'a' before calling 'g' and is assured that 'a' will be the same once 'g' is being executed by the transactional nature of 'f'; 'a' will either remain valid or 'f' will be aborted and retried.
  • Precondition wait semantics as introduced with SCOOP do not need to be used.
  • Class invariants determine the consistency of transactions and are checked every time a transaction is committed and after it is aborted

Deferred features:

  • Deferred features can be redefined to be either a transaction or not. As long as the feature satisfies its contract, the detail of whether the called feature is implemented as a transaction doesn't matter.

Agents:

  • Agent semantics will not change.

Mutexes:

  • Code using mutexes will continue to work, however they should be replaced with transactional code as soon as possible to avoid the possibility of deadlocks associated with locking.

Notes:

  • Unlike database transactions, durability is not guaranteed with feature transactions, memory is inherently volatile in the face of system errors.
  • It's impossible for a transactional feature to reliably act on a legacy external feature. During the execution of a transactional feature, any of the actions may be aborted and retried and since legacy external features cannot be aborted, there is no reliable way to undo that action.
  • It might be better to use a keyword to define a feature as non-transactional instead of using a keyword to define a feature as transactional.

Examples

Transactions are assured with transactional memory, probably implemented as software transactional memory.


Example of transaction:

feature
 
  correct_removal(container: DISPENSER) is
    transaction
        -- This is a transaction so it is assured to be atomic and isolated
      if
        not(container.is_empty)
      then
        container.remove
      end
    end

This feature is assured to be correct because is is isolated and atomic with respect to the system. If the container has been modified between the call to is_empty and remove, the feature would be aborted and retried.


feature
 
  incorrect_removal(container: DISPENSER) is
    do
      if
        not(container.is_empty)
      then
        container.remove
      end
    end

This is the standard example of concurrency issues with preconditions. The container can change between the call to is_empty and remove. Using transactions avoids this.


Legacy externals example

feature
 
  use_legacy_external(item: LEGACY_ITEM) is
    do
      print_item(item)
      log_item(item)
      -- At this point the runtime will block until print_item and 
      -- log_item have both committed, it will ensure nothing is running 
      -- in the system and then run the external item serially.  
      -- This is the non-concurrent way to ensure something executes as 
      -- a transaction, isolated and atomic.
      use_item(item)
    end
 
  use_item(item: LEGACY_ITEM) is
    external
      "..."
    end
 
  print_item(item: LEGACY_ITEM) is
    do
      ...
    end
 
  log_item(item: LEGACY_ITEM) is
    do
      ...
    end

Example of need for runtime checks on agents in systems that allow legacy external features.

class A
feature
  other: B
  legacy_external_feature is
    external
      "..."
    end
 
  call_transaction_with_agent is
    --This feature would compile since it would be undecidible if 'other' is attached to an instance of C at runtime
    do
      other.redefined_call(agent legacy_external_feature)
    end
 
  a_transaction is
    --This feature is a compile time error as a validity constraint
    transaction
      legacy_external_feature
    end
 
end
 
deferred class B
feature
  redefined_call(the_agent: PROCEDURE[TUPLE[]]) is
    --A reason to allow deferred features to be redefined
    --to a transaction or not is for syntax simplicity
    --and because the only time it matters is when building
    --new transactions on top of legacy code
    deferred
    end
end
 
class C
inherit B
feature
  redefined_call(the_agent: PROCEDURE[TUPLE[]]) is
    transaction
      io.put_string("Line 1")
 
      --This call is a runtime exception.  The probability of this happening
      --is low because people building transactional code should be looking
      --at replacing legacy external features with transactional externals
      --or some other transaction abstraction over externals
      the_agent.call
 
      io.put_string("Line 2")