Difference between revisions of "Transactions"

Revision as of 10:44, 9 April 2007

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.

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,

Rationale: The un-computability 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
• All feature calls are asynchronous
• Transactional features guarantee atomicity and isolation across the execution of the feature
• 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.
• 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.
• Features with preconditions and postconditions can only be called from a feature that is a transaction as a validation constraint.
• 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 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

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.

Agents:

• Agent semantics will not change.

Exceptions:

• The feature {ANY}.last_exception is obsolete
• 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:

• 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.
• 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:

• The thread library is obsolete. All classes should be marked obsolete.

Threads:

• 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:

• 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.

Legacy:

• 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.

• Building transactions over code that references legacy externals can cause runtime routine failures; the overlying solution would be to eliminate legacy external features.

• 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.

• External clauses without abort and commit clauses are called 'legacy externals' and are marked as obsolete by compilers supporting legacy externals.

• 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.

• 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.

• 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.

Notes:

• 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 completes. These two could actually run in parallel in the case where the first call writes nothing to the screen.

• 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.

• 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.

• 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.

• 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.

• 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.

• 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

The main thing to remember is that the proposal states that all features calls are asynchronous.

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.

Example of concurrency:

feature
 
  write_all_files is
    do
      write_file_1
      write_file_2
      write_file_3
      write_file_4
    end

Since all feature calls would be asynchronous, the four write_file features could be executed in parallel if the runtime decides to do so. This is not a transaction so isolation across these calls is not assured.

feature
 
  write_file is
    external
      "operating_system_write"
    abort
      "operating_system_abort"
    commit
      "operating_system_commit"

This is how transactional features can be mapped on to external function calls that support transactional operations

feature
 
  source: DISPENSER[ANY]
      -- Where items are taken from
  destination: DISPENSER[ANY]
      -- where items are put after processing
  running: BOOLEAN
      -- Flag to stop processing
 
  consumer is
    do
      from
      until
        not (running)
      loop 
          -- This loop will spawn multiple threads, microthreads, 
          -- hyperthreads, or whatever the implementation is and 
          -- runtime chooses, all processing a single item.
        process_single_item
      end
    end
 
  process_single_item is
    local
      item: ANY
    transaction
        -- Since this is a transaction, accessing the container 
        -- is safe even when run concurrently.
      if
        not source.is_empty
      then
        item := source.item
        source.remove
        io.put_string(item.to_string)
        destination.put(item)
      end
    end

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

Difference between a transaction and non-transaction

feature
 
  write_things_1 is
    transaction
      io.put_string("Line one")
      io.put_new_line
      io.put_string("Line two")
      io.put_new_line
    end

This feature is assured that line two will appear right after line one.

feature
 
  write_things_2 is
    do
      io.put_string("Line one")
      io.put_new_line
      io.put_string("Line two")
      io.put_new_line
    end

This feature is not assured that line two will appear after line one. Any number of lines could have been inserted between each by other paths of execution printing to the screen.

This is useful for disjoint functionality

Example of need for runtime checks on agents in systems that allow legacy external features. Once legacy external features are not used this check will not be necessary.

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")