Software Transaction memory

What is that about

 

OndŘej Chaloupka

int x = 0, y = 0, z = 0;
void first {
   x = x + 1;
}
void second {
  y = y + 1;
  x = x + 1;
}
void third {
  z = z + 1;
  y = y + 1;
  x = x + 1;
}

Running in pararell

int x = 0, y = 0, z = 0;
void first {
   x = x + 1;
}
void second {
  y = y + 1;
  x = x + 1;
}
void third {
  z = z + 1;
  y = y + 1;
  x = x + 1;
}

Running in pararell

x == 3, y == 2, z == 1 ???
int x = 0, y = 0, z = 0;
void first {
  synchronized(this) {
    x = x + 1;
  }
}
void second {
  synchronized(this) {
    y = y + 1;
    x = x + 1;
  }
}
void third {
  synchronized(this) {
    z = z + 1;
    y = y + 1;
    x = x + 1;
  }
}
x == 3, y == 2, z == 1 !
txn_int x = 0, y = 0, z = 0;
void first {
   atomic {
     x = x + 1;
   }
}
void second {
  atomic {
    y = y + 1;
    x = x + 1;
  }
}
void third {
  atomic {
    z = z + 1;
    y = y + 1;
    x = x + 1;
  }
}
x == 3, y == 2, z == 1 !!!
class Account {
  int balance;
  synchronized void withdraw(int n) {
    balance = balance - n; 
  }

  void deposit(int n) {
    withdraw(-n);
  }
}

class Transfer  {
  void transfer(Account from, Account to, int amount) {
    from.withdraw(amount);
    to.deposit(amount);
  }
}

Locks are not composable

class Account {
  int balance;
  synchronized void withdraw(int n) {
    balance = balance - n; 
  }

  void deposit(int n) {
    withdraw(-n);
  }
}

class Transfer  {
  void transfer(Account from, Account to, int amount) {
    synchronized(from) {
      synchronized(to) {
        from.withdraw(amount);
        to.deposit(amount);
      }
    }
  }
}
class Account {
  txn_int balance;
  void withdraw(int n) {
    atomic {
      balance = balance - n;
    }
  }

  void deposit(int n) {
    withdraw(-n);
  }
}

class Transfer  {
  void transfer(Account from, Account to, int amount) {
    atomic {
      from.withdraw(amount);
      to.deposit(amount);
    }
  }
}

Software transaction memory

  • A concurrency models which uses shared memory
  • An alternative to the lock-based synchronization approach
  • Grouping memory operations for them running atomically
  • Simple interface for developers
  • Can be implemented in various but not easy ways

Why "transactional" (STM)

  • ACI(D) properties for the program
    • Atomically - either all operations are done or non of them
    • Consistency
    • Isolation - no influencing each other
      • serializable - operations appears like processing one after another
        (even system hardly thrive to process in parallel)
    • D - not usual, Narayana uses transaction log store to provide  it

HOW IT WORKS

void second {
  atomic {
    y = y + 1;
    x = x + 1;
  }
}

Handle/Proxy

Memory

void third {
  atomic {
    z = z + 1;
    y = y + 1;
    x = x + 1;
  } 
}

HOW IT WORKS

void second {
  atomic {
    y = y + 1;
    x = x + 1;
  }
}

x =0

y =0

y =1

x =1

Memory

Write-set

read y

read x

Read-set

Narayana STM

public class Container<T> {
  public enum TYPE { RECOVERABLE, PERSISTENT };
  public enum MODEL { SHARED, EXCLUSIVE };
  public Container ();
  public synchronized T create (T member);
  public static final Container<?>
          getContainer (Object proxy);
}

Narayana STM

@Transactional
public interface StockLevel {
  int get () throws Exception;
  void set (int value) throws Exception;
  void decr (int value) throws Exception;
}

Narayana STM

Container<StockLevel> container = new Container<>();
StockLevelImpl stock = new StockLevelImpl();

StockLevel stockWrapped = container.create(stock);

// update the STM object inside a transaction
// or use annotations to define transaction boundaries
AtomicAction a = new AtomicAction();

a.begin();
stockWrapped.set(1234);
a.commit();

Narayana STM

// Implementations of interface
// are container managed
@Transactional

// Container will create
// a new transaction for each method
@Nested & @NestedTopLevel

@Optimistic & @Pessimistic

@ReadLock & @WriteLock

@State & @NotState

@TransactionFree

Resources