Fail OrElse….

A year or two ago, software transactional memory started getting mentioned all over the place. This is a technique for wrapping application locks in a way that hides the underlying locking from application programmers. Over the weekend, I though I’d have a play around implementing some of this technique using F#.
 
We’ll be using Dictionary objects to record the reads and writes that happen during the execution, so we need access to the .NET framework dictionary type.
 
#light;;
open System.Collections.Generic;;
 
A object behind the TransactionLog interface will manage a number of indexed locations of a fixed type (‘a). We will have to be able to see the value of a location as viewed via the lens of the transction (VisibleValue) and will be able to see if the transaction has read the value (TransactionHasRead). We will also be able to tell the transaction to commit (using Commit()). This will internally use an overloaded version of the method to do the work of committing.
 
type ‘a TransactionLog() =
  abstract VisibleValue : int -> ‘a
  abstract TransactionHasRead : int -> bool
  abstract Commit : unit -> bool
  abstract Commit : Dictionary<int, ‘a> list * Dictionary<int, ‘a> list -> bool
 
Our transactions will nest (so that we can later implement a way of combining transactions), but at the base level we’ll have an array of memory that has software transactions running on top of it.
 
type ‘a TransactionalMemory (memory : ‘a[]) =
  inherit TransactionLog<‘a>()
  override v.VisibleValue(index) = memory.[index]
  override v.TransactionHasRead(index) = false
  override v.Commit () = true
  override v.Commit (reads, writes) =
    lock memory
      (fun _ ->
        if List.for_all
          (fun (dict : Dictionary<int, ‘a>) ->
             Seq.for_all (fun key -> memory.[key] = dict.[key]) dict.Keys)
             reads
        then List.iter
               (fun (dict : Dictionary<int, ‘a>) ->
                    Seq.iter (fun key -> memory.[key] <- dict.[key]) dict.Keys)
               writes;
             true
        else false)
 
The Commit operation  takes a list of values that have been read by the sequence of nested transactions, ordered by outermost transaction first, and a list of locations that have been written by the transactions. It locks the memory, checks that the values of the locations are still as they were during the first reads that happened as part of the transaction, and then replays all of the writes. If the values are not as they were read during the transaction, the commit fails.
 
Sitting on top of the transaction memory, we have a series of nested transactions.
 
type ‘a NestedTransaction (innerTransaction : TransactionLog<‘a>) =
  inherit TransactionLog<‘a>() as base
  let reads = new System.Collections.Generic.Dictionary<int, ‘a>()
  let writes = new System.Collections.Generic.Dictionary<int, ‘a>()
  override v.VisibleValue(index) =
    let success, value = writes.TryGetValue(index)
    if success
    then value
    else innerTransaction.VisibleValue(index)
  override v.TransactionHasRead(index) =
    reads.ContainsKey(index) || innerTransaction.TransactionHasRead(index)
  member v.Read(index) =
    if v.TransactionHasRead(index)
    then v.VisibleValue(index)
    else
      let visibleValue = innerTransaction.VisibleValue(index)
      (reads.Add(index, visibleValue); visibleValue)
  member v.Write(index, value) =
    writes.[index] <- value
  override v.Commit() =
    v.Commit([reads], [writes])
  override v.Commit(all_reads, all_writes) =
    innerTransaction.Commit (reads::all_reads, writes::all_writes)
 
We can quickly try out the code:
 
> let test = [| 0; 0; 0; 0; |];;
val test : int array
> let transactionalBlock = new TransactionalMemory<int>(test);;
val transactionalBlock : int TransactionalMemory
> let transactionOverMemory = new NestedTransaction<int>(transactionalBlock);;
val transactionOverMemory : int NestedTransaction
> transactionOverMemory.Read(0);;
val it : int = 0
> transactionOverMemory.Write(0, 10);;
val it : unit = ()
> test;;
val it : int array = [|0; 0; 0; 0|]
> transactionOverMemory.Commit();;
val it : bool = true
> test;;
val it : int array = [|10; 0; 0; 0|]
 
However, if the value is changed before we run the transaction, it fails to commit.
 
> let test = [| 0; 0; 0; 0; |];;
val test : int array
> let transactionalBlock = new TransactionalMemory<int>(test);;
val transactionalBlock : int TransactionalMemory
> let transactionOverMemory = new NestedTransaction<int>(transactionalBlock);;
val transactionOverMemory : int NestedTransaction
> transactionOverMemory.Read(0);;
val it : int = 0
> transactionOverMemory.Write(0, 10);;
val it : unit = ()
> test.[0] <- 20;;
val it : unit = ()
> test;;
val it : int array = [|20; 0; 0; 0|]
> transactionOverMemory.Commit();;
val it : bool = false
> test;;
val it : int array = [|20; 0; 0; 0|]
 
That’s all well and good, but what we really need if a more consise syntax for expressing transactions. F# has a way of doing this using computation expressions or workflows. These offer some of the facilities of monads.
 
type TransactionBuilder() =
  member v.Return(x) = fun transaction -> failwith "Transactions have no value"
  member v.Bind(p, rest) =
    fun transaction ->
      match p transaction with
       (result, currentTransaction) -> rest result currentTransaction
  member v.Let(p, rest) = fun transaction -> rest p transaction
  member v.Delay(f) =  f()
  member v.Zero () = fun transaction -> transaction
let transaction = new TransactionBuilder()
let ReadTVal index (v : ‘a NestedTransaction) = (v.Read(index), v)
let WriteTVal index value (v : ‘a NestedTransaction) = (v.Write(index,value), v)
 
We can now write out transactions in a more consise manner.
 
> let transaction1 =
–   transaction {
–                let! x = ReadTVal(0)
–                let newValue = x + 1
–                do! WriteTVal 0 (x+1)
–               } ;;
val transaction1 : (int NestedTransaction -> int NestedTransaction)
 
And we can try this transaction out.
 
> let test = [| 0; 0; 0; 0; |];;
val test : int array
> let transactionalBlock = new TransactionalMemory<int>(test);;
val transactionalBlock : int TransactionalMemory
> let transactionOverMemory = new NestedTransaction<int>(transactionalBlock);;
val transactionOverMemory : int NestedTransaction
> let resultingTransaction  = transaction1 transactionOverMemory;;
val resultingTransaction : int NestedTransaction
> test;;
val it : int array = [|0; 0; 0; 0|]
> resultingTransaction.Commit();;
val it : bool = true
> test;;
val it : int array = [|1; 0; 0; 0|]
 
The workflow expression needs a little explaining, but I would like to leave that until another blog post on quasi-quoting in F#. Suffice it to say that the front end of the F# compiler will do transformation for certain expressions with syntax expr { …}
 
We are getting there but we would like more. First it would be nice to allow transactions to be failed by calls inside the code. This will give us the ability to decide at runtime whether the transaction is allowed to proceed.
 
F# has a type named option that can be used to wrap values while offering an additional null value.
 
> Some 10;;
val it : int option = Some 10
> None;;
val it : ‘a option = None
 
Instead of passing NestedTransaction values around, we’ll pass NestedTransaction option values where the None case is used to represent an aborted transaction.
 
 type TransactionBuilder() =
  member v.Return(x) = fun transaction -> failwith "Transactions have no value"
  member v.Bind(p, rest) =
    fun transaction ->
     match transaction with
      | None -> None
      | Some carriedTransaction ->  
          match p carriedTransaction with
           | None -> None
           | Some (result, currentTransaction) -> rest result (Some currentTransaction)
  member v.Let(p, rest) =
    fun transaction ->
      match transaction with
       | None -> None
       | Some current -> rest p (Some current)
  member v.Delay(f) =  f()
  member v.Zero () = fun transaction -> transaction
  member v.Combine (p,q) =
    fun transaction ->
      match transaction with
        None -> None
      | carriedTransaction ->
          match p carriedTransaction with
            None -> None
          | resultTransaction -> q resultTransaction
 
let transaction = new TransactionBuilder()
 
We can now define fail.
 
let fail = fun transaction -> None
 
We have to redefine the read and write values code.
 
let ReadTVal index (v : ‘a NestedTransaction) = Some (v.Read(index), v)
let WriteTVal index value (v : ‘a NestedTransaction) = Some (v.Write(index,value), v)
 
We can now define a transaction that increments only if the value is greater than zero.
 
let transaction2 =
  transaction { let! x = ReadTVal(0)
                if x=0 then return! fail
                let newValue = x + 1
                do! WriteTVal 0 (x+1)
                 }
 
Next we can define something that run a transaction and commits.
 
let runAndCommitTransaction action (memory : ‘a array) =
  let transactionalBlock = new TransactionalMemory<‘a>(memory)
  let transactionOverMemory = new NestedTransaction<‘a>(transactionalBlock)
  let finalTransaction = action (Some transactionOverMemory)
  match finalTransaction with
    None -> false
  | Some (transaction : ‘a NestedTransaction) -> transaction.Commit()
 
We can test it out as follows.
 
 > let test = [| 0;1;2;3;4; |];;
val test : int array
>  runAndCommitTransaction transaction2 test;;
val it : bool = false
> let test = [| 0;1;2;3;4; |];;
val test : int array
> test.[0] <- 10;;
val it : unit = ()
>  runAndCommitTransaction transaction2 test;;
val it : bool = true
> test;;
val it : int array = [|11; 1; 2; 3; 4|]
 
These kinds of transactios are very powerful in that they are composable. We can define higher level operations to compose them.
 
The first, Then, takes two transactions and runs one before the other, failing if either fails.
 
let Then action1 action2 =
  fun transaction ->
    match transaction with
      None -> None
    | Some _ as currentTransaction -> 
      match action1 currentTransaction  with
        None -> None
      | result -> action2 result
 
The second, OrElse, takes two transactions. Its result is the result of the first transaction if that is successful, or the result of the second if the first transaction fails.
let OrElse action1 action2 =
  fun transaction ->
    match transaction with
      None -> None
    | Some currentTransaction ->
        let nestedTransaction = new NestedTransaction<int>(currentTransaction)
        match action1 (Some nestedTransaction) with
          None ->
            let nestedTransaction2 = new NestedTransaction<int>(currentTransaction)
            action2 (Some nestedTransaction2)
        | result -> result
 
 We could now define two predicates for testing a transactional location for zero and a means for incrementing it.
 
let incrementLocation index =
  transaction { let! current = ReadTVal index
                let newValue = current + 1
                do! WriteTVal index newValue
              }
 
let checkLocationValue index value =
  transaction { let! current = ReadTVal(index)
                if current = 0 then return! fail
              }
 
We can now define a composite transaction.
 
let testTransaction transaction =
  OrElse (Then (checkLocationValue 0 0)
               (incrementLocation 0))
         (Then (checkLocationValue 1 0)
               (incrementLocation 1))
         transaction;;
 
If the first branch of the OrElse is applicable, the composite transaction only depends on the first transactional location not changing value to enable a commit.
 
let test = [| 2; 0; 0; 0; |];;
let transactionalBlock = new TransactionalMemory<int>(test);;
let transactionOverMemory = new NestedTransaction<int>(transactionalBlock)
let result = match testTransaction (Some transactionOverMemory)  with Some x -> x;;
> result.TransactionHasRead 0;;
val it : bool = true
> result.TransactionHasRead 1;;
val it : bool = false
> result.Commit();;
val it : bool = true
> test;;
val it : int array = [|3; 0; 0; 0|]
 
Likewise, if the second branch takes effect, then the only precondition is the second transactional location.
 
let test = [| 0; 2; 0; 0; |];;
let transactionalBlock = new TransactionalMemory<int>(test);;
let transactionOverMemory = new NestedTransaction<int>(transactionalBlock)
let result =  match testTransaction (Some transactionOverMemory)  with Some x -> x;;
 
> result.TransactionHasRead 0;;
val it : bool = false
> result.TransactionHasRead 1;;
val it : bool = true
> result.Commit();;
val it : bool = true
> test;;
val it : int array = [|0; 3; 0; 0|]
 
The transaction will fail if neither branch is applicable.
 
let test = [| 0; 0; 0; 0; |];;
let transactionalBlock = new TransactionalMemory<int>(test);;
let transactionOverMemory = new NestedTransaction<int>(transactionalBlock)
 
> testTransaction (Some transactionOverMemory) ;;
val it : int NestedTransaction option = None
 
And will still fail if the precondition is invalidated.
 
let test = [| 2; 0; 0; 0; |];;
let transactionalBlock = new TransactionalMemory<int>(test);;
let transactionOverMemory = new NestedTransaction<int>(transactionalBlock)
let result = match testTransaction (Some transactionOverMemory)  with Some x -> x;;
test.[0] <- 20;;
 
> result.Commit();;
val it : bool = false
 
Transactional memory has given us a means of doing transactions without needing to do any locking at the user code level, whilst offering us the ability to define mechanisms for composing transactions in really powerful ways. Most articles go on to define, Retry, a primitive that causes the transaction to be repeated. Some implementations of this use the locations read set to avoid (in the context of functional transactions) re-executing the transaction until the values that the transaction previously read have changed. Essentially we could do this by having a third alternative to Some/None which passes back the read collection for the retrying collection.
 
Like all abstractions there are disadvantages to this kind of scheme. For the small number of lines of code it takes to implement it, it is a powerful abstraction though.
 
 
Advertisements
This entry was posted in Computers and Internet. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s