This section explains mechanisms used in Tamino for database access from concurrent transactions. It explains the terms used and discusses the available isolation levels and their effect on the various concurrency phenomena.

The topics described in this document are:

• The Hierarchical Locking Concept of Tamino

• Concurrency Phenomena in DBMS

• Isolation Levels in Tamino

• Isolation Levels and Concurrency Phenomena

• Lifetime of Locks

• General Rules for the Choice of the Isolation Level

---

The Hierarchical Locking Concept of Tamino

Tamino's hierarchical locking concept is introduced here under the headings:

• Locking Granularities

• Lock Modes

Locking Granularities

Tamino makes use of a hierarchical locking system to implement isolation levels. A hierarchical locking system is characterized by the fact that locks may be set on different granularities. A lock set on a higher granularity implicitly sets the same lock on the lower granularities. The locking system in Tamino currently recognizes the following hierarchy of granularities:

1. database

2. collection

3. doctype

4. document

In practice, the highest level on which Tamino may set a lock is the level of a collection; a full database lock is never set.

Lock Modes

A locking system works with a set of different lock types, ranging from weaker to stronger locks. During its lifetime (normally within a transaction) a weaker lock set on an object may be escalated to a stronger lock.

In total, Tamino makes use of six lock types. They can be coarsely divided into two groups each consisting of three lock types. The first group contains lock types which affect objects directly; the second group contains lock types which represent an intention to lock further objects at a finer granularity.

The explicit lock types are:

1. No lock
   This mode represents the absence of any locks. In Tamino this mode is indicated by the term "unprotected".

2. Share (S)
   Provides the right to read the object at the granularity on which the lock is set or any object at a finer granularity and prevents concurrent transactions from holding IX, X or SIX locks. In Tamino this mode is indicated by the term "shared".

3. eXclusive (X)
   Provides the right to write the object at the granularity on which the lock is set as well as the right to set any lock on a finer granularity and prevents concurrent transactions from holding any locks on this or any finer granularity. In Tamino this mode is indicated by the term "protected".

The intention lock types are:

1. Intention Share (IS)
   Provides the right to set S or IS locks at a finer granularity and prevents concurrent transactions from holding X locks on this granularity.

2. Intention eXclusive (IX).
   Provides the right to set S, IS, X, IX or SIX locks at a finer granularity and prevents concurrent transactions from holding S, X or SIX locks on this granularity.

3. Share and Intention eXclusive (SIX)
   Provides the right to read the object at the granularity on which the lock is set or any object at a finer granularity and prevents concurrent transactions from holding S, IX, X or SIX locks. In addition it provides the right to set IX and X locks at a finer granularity. The SIX lock is essentially a union between lock types S and IX.

The following table summarizes the compatibilities of the above mentioned lock types.

	Already granted lock
Requested lock IS IX S SIX X	No Lock IS IX S SIX X + + + + + - + + + - - - + + - + - - + + - - - - + - - - - -

Example

The following scenario gives an example how hierarchical locks are used.

Assume a transaction T1 in which all accounts that currently have a balance of more than 5000 $ need to be processed. This transaction is running in parallel to other transactions which add and subtract sums from accounts. The requirement for T1 is that it is guaranteed that all accounts with a balance of more than 5000 $ are found and also that no transfers are made that would possibly result in an account to drop below 5000 $ or increase to more than 5000 $ while T1 is executing. This can be achieved by T1 setting an "S" lock on the doctype in which all the account documents reside. All other parallel transactions that would like to make modifications to an account set an "IX" lock on the doctype (indicating the intent to set an "X" lock on one or more documents in the doctype). The "IX" and "S" locks on the doctype are incompatible. That means that T1 needs to wait until all existing "IX" locks have been relinquished, and once T1 has acquired the "S" lock, all other transactions need to wait for their "IX" lock until T1 has finished. In the following sections it will become clear that in Tamino this behavior is achieved by executing T1 in isolation level "serializable".

Concurrency Phenomena in DBMS

In databases (Tamino as well as relational databases), various possible scenarios can be considered that might occur in concurrent transaction processing. The chosen isolation level determines whether these phenomena may occur or not.

In the following, the most commonly known concurrency phenomena are described:

• Lost Updates

• Dirty Read Operation

• Non-repeatable Read Operation

• The Phantom Effect

Lost Updates

The lost update phenomenon occurs when two or more concurrent transactions read and update the same data.

Lost updates represent a kind of write/write-dependency. The following situation will lead to the occurrence of lost updates:

1. Transaction 1 reads a document.

2. Transaction 2 then reads exactly the same document.

3. Transaction 1 modifies the document.

4. Transaction 2 modifies the document.

Regardless of whether the commit is accepted or rejected, there would be one update lost in this situation!

Dirty Read Operation

The dirty read phenomenon may occur when a transaction modifies data and another transaction reads the same data before the first transaction is committed or rolled back.

1. Transaction 1 reads a document.

2. Transaction 1 modifies the document.

3. Transaction 2 then reads exactly this modified document before a commit is performed on transaction 1.

4. Transaction 1 performs a roll back.

   The result of this scenario is that transaction 2 has read incorrect ("dirty") data that has never been committed because transaction 1 has been rolled back afterwards.

Non-repeatable Read Operation

Non-repeatable read phenomena may occur when one transaction reads and modifies data and the same data is a read by a concurrent transaction multiple times:

The following situation will lead to the occurrence of such phenomena:

1. Transaction 2 reads a document.

2. Transaction 1 then reads exactly the same document.

3. Transaction 1 modifies the document.

4. Transaction 1 performs a commit.

5. Transaction 2 reads the same document again.

The result of the two identical read operations of transaction 2 will not be the same. This might lead to inconsistencies.

The Phantom Effect

The phantom phenomenon may occur when one transaction establishes a set of documents as the result of a query and other concurrent transactions insert or delete documents which would have been part of that set.

1. Transaction 1 reads some data that fulfills some search condition.

2. Transaction 2 inserts a document which would have been part of the result set calculated by transaction 1.

3. Transaction 3 deletes a document which was part of the result set calculated by transaction 1.

4. Both transaction 2 and transaction 3 commit.

5. Transaction 1 executes the same query. The results are different.

Isolation Levels in Tamino

As explained in the previous sections, a number of consistency phenomena may occur as soon as transactions can execute in parallel. In an ideal world, each transaction would be completely isolated from all other concurrently executed transactions and none of the above mentioned consistency phenomena would occur. It is clear however that this would require that to a large extent operations would have to be serialized. On the other hand not every application has the requirement that none of the consistency phenomena may occur. Some applications can live very well with a lower level of consistency.

The question is therefore always to find the right balance between the consistency requirements on the one hand and the maximization of parallelizing transactions on the other. For this purpose Tamino offers a number of isolation levels, each providing a different level of consistency. The isolation level of a transaction defines the degree of visibility of intermediate states of documents as produced by other concurrent transaction in the database. It is important to understand that the isolation level of a transaction does not determine to what degree intermediate states produced by this transaction are visible to other transactions.

Tamino supports the following isolation levels which are listed in order of ascending degree of isolation:

• "uncommittedDocument"

• "committedCommand"

• "stableCursor"

• "stableDocument"

• "serializable"

The default values are:

• In a session context, the default is "stableDocument".

• In a session-less context, the default is "uncommittedDocument", unless an XQuery update command is issued. In that case the isolation level is automatically upgraded to "committedCommand", the next stronger isolation level.

In the following sections, each one of the isolation levels is described. The description of each isolation level includes a table which shows exactly which locks are set on the collection, doctype and document granularities for all relevant operations. The operations listed are:

• query
  These are either X-Query or XQuery queries which retrieve documents or parts thereof from the database or direct access via similar plain URL addressing.

• process
  These are _process commands which either insert a new document or update an existing one.

• delete
  These are _delete commands which delete existing documents from the database.

• update(read)
  These are the query parts of an XQuery update command.

• update(write)
  These are the update parts of an XQuery update command.

• define
  These are _define commands.

• undefine
  These are _undefine commands.

As the setting of the lockMode parameter also has an influence on the locking behaviour of Tamino, this is indicated in a separate column.

Note that the expression "sensitive XQuery cursor" is used to indicate a cursor over an XQuery query which is labeled to be "sensitive", i.e. the parameter _sensitive has been set to the value "vague". This implies that the result of the query is not calculated at cursor open time but on the fly.

For more information see The _cursor command in Requests using X-Machine Commands.

Isolation Level "uncommittedDocument"

This value is the default value for the isolation level parameter if used in database operations in a session-less context.

In this isolation level the dirty-read situation can occur:

A command within a transaction with this isolation level can read a so-called "dirty" document at any time, which means that a concurrent transaction has changed the document but might abort later on.

Another possible situation leading to incorrect results:

The document content might be outdated in the sense that a concurrent transaction has changed the content after the current transaction has read it.

This isolation level only protects against lost updates and dirty writes, but not against any other of the above mentioned concurrency phenomena.

A command can also modify a document if no concurrent transaction is modifying the document, or no other transaction requires the document to be in a stable state (isolation level "stableCursor" and higher).

The characteristics of isolation level "uncommittedDocument" are:

• No lost updates.

• No dirty writes/updates.

• Dirty read is possible.

• Read any document at any time.

• Exclusive locks on documents persist until end of transaction.

• For queries using _xql: No shared locks.

• For queries using _xquery: No shared locks with insensitive cursors but shared lock with sensitive cursors.

The following table shows which kinds of locks are applied in isolation level "uncommittedDocument" depending on database operation and affected granularity:

	Lock Types for Isolation Level "uncommittedDocument"
Action query       process delete update (read) update (write) [up]define undefine	Lock Mode Collection Doctype Document ./. IS IS *) unprotected IS IS **) shared IS IS S protected IX IX X   IX IX X   IX IX X ***) ***) ***) ***) ***) ***) ***) ***)   X       X

*) S for sensitive XQuery cursors, no lock otherwise.

**) not allowed with sensitive XQuery cursors, no lock otherwise.

***) not applicable. The isolation level "uncommittedDocument" is not possible for XQuery update commands.

Isolation Level "committedCommand"

A command within a transaction in this isolation level can read documents that have been modified, inserted or updated by committed transactions but not documents that have been modified, inserted or updated by concurrent transactions. This means that the transaction only sees document states that have been committed but might have been changed by faster concurrent transactions.

The characteristics of isolation level "committedCommand" are:

• No lost updates.

• No dirty writes.

• Only read results of committed transactions (i.e. no dirty read is possible).

• Non-repeatable read is still possible.

• Exclusive locks on documents persist until end of transaction.

• Shared locks for query execution persisting for the duration of a command.

This isolation level protects against dirty reads, but not against non-repeatable reads.

The following table shows which kinds of locks are applied in isolation level "committedCommand" depending on database operation and affected granularity:

	Lock Types for Isolation Level "committedCommand"
Action query       process delete update (read) update (write) [up]define undefine	Lock Mode Collection Doctype Document ./. IS IS S *) unprotected IS IS **) shared IS IS S protected IX IX X   IX IX X   IX IX X see query ***) IX IX see query unchanged unchanged unchanged X   X       X

*) S for sensitive XQuery cursors. This S lock only exists temporarily. In all other cases no lock is held.

**) not allowed with sensitive XQuery cursors.

***) not allowed with lock mode "unprotected"

Isolation Level "stableCursor"

A transaction with this isolation level guarantees that a document in the cursor result set will not be changed by concurrent transactions (i.e. will still match the query predicate) in the following cases:

• In the case of a non-scrollable cursor: until the document has been returned to the requesting application and the document is no longer in the current fetch set of the cursor.

• In the case of a scrollable cursor: as long as the cursor exists.

The characteristics of isolation level "stableCursor" are:

• No lost updates.

• No dirty writes.

• Only read results of committed transactions (i.e. no dirty read is possible).

• Keep data in cursor stable until it is no more accessible.

• Exclusive locks on documents persist until end of transaction.

• Shared locks for query execution until data no more accessible in cursor.

The following table shows which kinds of locks are applied in isolation level "stableCursor" depending on database operation and affected granularity:

	Lock Types for Isolation Level "stableCursor"
Action query       process delete update (read) update (write) [up]define undefine	Lock Mode Collection Doctype Document ./. IS IS S *) unprotected IS IS **) shared IS IS S protected IX IX X   IX IX X   IX IX X see query ***) IX IX see query unchanged unchanged unchanged X   X       X

*) S for sensitive XQuery cursors

**) not allowed with sensitive XQuery cursors, no lock otherwise

***) not allowed with lock mode "unprotected"

Isolation Level "stableDocument"

This value is the default value for the isolation level parameter of transactions within a session context.

This isolation level guarantees that a document that has been read within the current transaction cannot be changed by a concurrent transaction until the end of the current transaction. Unqualified documents can be modified or deleted, new documents can be inserted.

The characteristics of isolation level "stableDocument" are:

• There are no lost updates.

• There are no dirty writes.

• Only read results of committed transactions can be obtained (i.e. no dirty read is possible).

• Keep documents stable until end of transaction (repeatable read).

• Exclusive locks on documents persist until end of transaction.

• Shared locks are used for query result until end of transaction.

This isolation level protects against non-repeatable reads, but not against phantom effects.

The following table shows which kinds of locks are applied in isolation level "stableDocument" depending on database operation and affected granularity:

	Lock Types for Isolation Level "stableDocument"
Action query       process delete update (read) update (write) [up]define undefine	Lock Mode Collection Doctype Document ./. IS IS S unprotected IS IS **) shared IS IS S protected IX IX X   IX IX X   IX IX X see query ***) IX IX see query unchanged unchanged unchanged X   X       X

**) not allowed with sensitive XQuery cursors, no lock otherwise

***) not allowed with lock mode "unprotected"

Isolation Level "serializable"

This isolation level guarantees the independence of the result set of a query from any influence by concurrent transactions. This means that the query result will always be the same.

Isolation level "serializable" protects against all kinds of concurrency phenomena including phantom effects.

The characteristics of isolation level "serializable" are:

• There are no lost updates.

• There are no dirty writes.

• Repeatable read is guaranteed.

• Exclusive and shared locks on documents persist until end of transaction.

• Shared locks on a higher level apply not only on already existing documents, but also prevent input of new documents that influence query results.

The following table shows which kinds of locks are applied in isolation level "serializable" depending on database operation and affected granularity:

	Lock Types for Isolation Level "serializable"
Action query       process delete update (read) update (write) [up]define undefine	Lock Mode Collection Doctype Document ./. IS S *) *) unprotected IS IS **) shared IS S   protected IX SIX X   IX SIX X   IX SIX X see query ***) IX SIX see query unchanged unchanged unchanged X   X       X

*) There is a special handling for _xql=doctype[@ino:id=?] : IS is applied on doctype level, S is applied on document level. The same applies for an equivalent XQuery.

**) Not allowed with sensitive XQuery cursors, no lock otherwise

***) Not allowed with lock mode "unprotected"

Isolation Levels and Concurrency Phenomena

The Dependence between Concurrency Phenomena and Isolation Levels

The relationship between isolation levels and the types of concurrency phenomena which are allowed or forbidden for the individual isolation level can also be expressed in a table:

Isolation Levels and Concurrency Phenomena	Concurrency Phenomenon
Isolation level "uncommittedDocument" "committedCommand" "stableCursor" "stableDocument" "serializable"	Lost Update Dirty Read Dirty Write Non-repeatable Read Phantom Effect No Yes No Yes Yes No No No Yes Yes No No No Not in cursor Yes No No No No Yes No No No No No

The table shows for each isolation level which concurrency phenomena are possible.

Lifetime of Locks

In order to be able to achieve a detailed understanding of locking it is essential to know how long a lock will live. In Tamino, the duration how long locks are held depends on:

• the type of the lock.

• and the chosen isolation level.

The following rules apply:

• IS, IX and SIX locks
  All intention locks (IS, IX and SIX) are kept for the duration of the transaction.

• X locks
  All X locks are also kept for the duration of a transaction.

• S locks
  In all cases where _lockMode is set to "shared", the S locks are kept until the end of the transaction.

  Otherwise, the amount of time that an S lock is kept depends on the isolation level:

  Dependence of the Duration of Locks from Isolation Level

  Isolation Level	Lifetime of Locks
  "uncommittedDocument"	no S locks are set. *)
  "committedCommand"	S locks are kept for the duration of the command. *)
  "stableCursor"	S locks are kept for the duration of the cursor.
  "stableDocument"	S locks are kept for the duration of the transaction.
  "serializable"	S locks are not explicitly set on the document granularity, S locks set on any coarser granularity are kept for the duration of the transaction.

  Note:
  *) except for sensitive XQuery cursors. In that case S locks are kept for the duration of the transaction. This may be subject of change, however.

General Rules for the Choice of the Isolation Level

The choice of the isolation level should be made on the basis of the following considerations:

1. The higher the isolation level, the lower the influences from other transactions. Setting the isolation level to the highest possible value "serializable" means in fact providing a virtual database to each transaction. You can consider a virtual database as a database where each transaction is totally isolated from effects of other transactions.

2. The higher the isolation level, the higher the potential impact on the performance. Performance may be deteriorated for instance by too many deadlock situations occurring between concurrent transactions or quasi-sequential execution of concurrent transactions caused by a too restrictive isolation level setting.

3. Keep in mind that isolation levels are technically based on internal locks which will affect more documents with increasing degree of isolation. For instance, increasing the isolation level can mean that not only one single document but its whole doctype is locked. Similarly, the time for which an object is locked may increase significantly by choosing a higher level of isolation.

4. It is important to understand that Tamino applies locks for query commands based on the index processing during the evaluation of the query. This means that depending on which indices are available and which of those are used to evaluate a query documents are locked. In other words it may well be the case that more documents are locked than those that are returned as the result of the query. Having appropriate indices defined is therefore not only important for the speed of queries but also minimizes the number of database objects that are affected by locks.

These considerations generally apply for all databases, they are not specific to Tamino.

The choice of the adequate isolation level means to find a reasonable compromise in such a way that you gain as much isolation, synchronization and performance as you need.