Chapter 12: Transactions and Concurrence Control
---


- transaction: sequence of server operations that is guaranteed to be
  atomic;

- servers must guarantee that either the entire transaction is carried
  out and the results recorded in permanent storage or, in the case
  that one or more of them crashes, its effects are completely erased;

- the synchronized keyword in Java locks the whole object, i.e., works
  just like a monitor;  no other synchronized method can be invoked;

- wait/notify in Java implement the semantics of condition variables;

- blocking vs. polling ;

- atomicity: all-or-nothing (failure atomicity, durability) + isolation;

- to support the requirement for failure atomicity and durability, the
  object must be recoverable;

- one way to achieve isolation is to perform operations serially;
  however, this leads to poor utilization and performance;

- ACID: Atomicity, Consistency, Isolation, Duratiliby;

- transactions can be committed or aborted;

- problems: lost update, inconsistent retrievals;

- serial equivalence: interleaving of the operations of transactions
  in which the combined result is the same as if the transactions had
  been performed one at a time in some order;

- conflicting operations: the combined results depends in the order of
  execution;

* for two transactions to be serially equivalent, it is necessary and
* sufficient that all pairs of conflicting operations of the two
* transactions be executed in the same order at all of the objects they
* both access;

- dirty reads: a transaction T2 reads a value written by a transaction
  T1 that is going to abort;

- recoverability of transactions: T2 must commit after T1, and if and
  only if T1 also commits;

	- this may cause cascading aborts;

- better solution: avoid dirty reads altogether;

- the premature writes problem can occur because systems usually
  perform recovery using a backed up value (also called the "before 
  image") for objects involved in a transaction.  Depending on which
  value is used as the backup, inconsistent states may occur as a
  result of aborted transactions.

- strict execution: both dirty reads and premature writes are avoided,
  relying just on results from commited operations;

- tentative versions is a way to isolate partial results from a
  transaction from the others;

- advantages of nested transactions:

	- subtransactions can run in parallel;
	- subtransactions can commit or abort independently;

- when a parent aborts, all of its subtransactions are aborted;  the
  inverse may not be true;

- if the top-level transaction commits, then all of the
  subtransactions that have provisionally commited can commit too;

- serialization can be done by the use of exclusive locks;

- transactiosn have a "growing phase" (during which locks are
  acquired) and a "shrinking phase" (when locks are released).  This
  is called TWO-PHASE LOCKING (TPL);

- strict TPL: locks are held until transaction commits or aborts;

- locking granularity is very important;

- multiple readers/single writers: read locks and write locks;

- in nested transactions, locks are passed from child to parent.
  Locks acquired by children are inherited by its parent.  A child can
  temporarily acquire a lock from its parent; subtransactions at the
  same level will take turns to acquire the locks held by their
  parent;

- timeouts are also used to prevent deadlocks;

- two-version locking: 3 types of locks: read, write, and commit.
  Here, read operations are delayed only while the transactions are
  being committed rather than during the entire execution of
  transactions.  On the other hand, reads of one transaction can 
  cause delay in committing other transactions;

- hierarchic locks use different granularities;

- disadvantages of locking:

	- lock maintenance overhead;
	- deadlocks;
	- cascading aborts;

- optimistic concurrency control:

	- a transaction issues just a closeTransaction request at the
	  end;

	- working phase: read/writes are satisfied locally (first read
 	  reads latest committed value).  Dirty objects represent
   	  tentative values and are not visible to other transactions;

	- validation phase: starts after the closeTransaction request.
	  Transaction is validated to see whether or not its actions 
	  conflicted with operations from other transactions;

	- update phase: validated transactions have their tentative
	  values made permanent;

- transactions get increasing TIDs when they enter the validation phase;

- as validation is short, can be serialized;

- backward vs. forward validation;

- backward validation of Tv:

	- read operations of earlier overlapping transactions (performed
	  before validation of Tv) cannot be affected by the writes ot Tv.
	  The validation checks Tv's read set against write sets of earlier
	  transactions, failing if there is any conflict;

- forward validation of Tv:

	- write set of Tv is compared with the read sets of all overlapping
	  active transactions;

	- differently from backward validation, in forward validation there
	  are choices of which transaction to abort (Tv or any of the
	  conflicting active transactions);

	- the action sets during validaton are bigger for BV than for FV;

- Timestamp ordering
  ------------------

- each operation in a transaction is validated when it is carried out.  If
  it cannot be validated, the transaction is aborted immediately;

- a transaction's request to write an object is valid only if that object
  was last read and written by earlier transactions.  A transaction's
  request to read an object is valid only if that object was last written by
  an earlier transaction;

- validating Tc:

	- Tc must not write an object that has been read by any Ti s.t.
	  Ti>Tc, i.e., Tc>=max read timestamp of the object;

	- the same rule above, when Ti has written the object;

	- Tc must not read an object that has been written by any Ti s.t.
	  Ti>Tc (Tc>= write timestamp of committed object);

- in the case of the read operation, Tc may need to wait for transactions
  with previous tentative values Tt s.t. timestamp < Tt <= Tc;

- multiversion timestamp ordering:
	
	- multiple timestamped versions of an object are kept, allowing
	  some of the "late reads" to proceed;

- Comparison of concurrency control mechanisms:

	- all limit, to some extent, the potential for concurrent
	  operation;

	- TPL and timestamp ordering are pessimistic;

	- timestamp ordering (TO) is better than strict TPL for read-only
	  transactions;

	- TPL is better when updates are frequent (no need to abort active
	  transactions??);


	Concurrency control
		+------------------------ TPL
		|
		+------------------------ TO ------------ Multiversion TO
		|
		+------------------------ Optimistic
						+-------- Forward Validation
						|
						+-------- Backward Validation