com.bigdata.btree.isolation

Class IsolatedFusedView

java.lang.Object

com.bigdata.btree.view.FusedView

com.bigdata.btree.isolation.IsolatedFusedView

All Implemented Interfaces:

IAutoboxBTree, IIndex, IIndexLocalCounter, ILocalBTreeView, IRangeQuery, ISimpleBTree, ICounterSetAccess

public class IsolatedFusedView
extends FusedView

An index (or index partition) that has been isolated by a transaction. Isolation is achieved by the following mechanisms:

1. The writeSet of the transaction on the index is isolated on a BTree visible only to that transaction.
2. Version timestamps are maintained for index entries in both the isolated write set and groundState from which the transaction is reading.
3. The groundState is defined as the view of the index (partition) as of the abs(startTime) of the transaction.
4. Reads are performed against an ordered view defined by the writeSet followed by the ordered set of indices defining the groundState of the index.
5. Writes first read through the ordered view to locate the most recent version for an index entry. If the index entry is located in the isolated writeSet then it is overwritten and its timestamp is unchanged. If the index entry is located in the groundState then the timestamp is copied from that index entry and written on the new version in the isolated writeSet.
6. During validation, version timestamps in the isolated writeSet are compared against the then current view of the corresponding unisolated index. If the timestamp in the unisolated view differs from that in the writeSet then there is a write-write conflict. Write-write conflicts MAY be validated if the index has a registered IConflictResolver.
7. If the writeSet is validated then it is mergedDown (copied onto) the then current unisolated index view. During the mergeDown phase the revision timestamp of the transaction is applied to all index entries copied from the write set. Transactions that later try to commit will recognize write-write conflicts based on those updated timestamps. Note that revision timestamps ARE NOT commit timestamps. Revision timestamps are assigned at the start of the validation phase. All tuples modified by a transaction are annotated with the same revision timestamp during the validation phase of the transaction. Write-write conflicts are detected on the basis of the per-tuple revision timestamps. Commit timestamps are assigned once the write set has been validated and checkpointed and all shards participating in the commit protocol signal that they are prepared and ready to commit.

Note: The timestamp from which the post-commit state of the transaction may be read IS NOT defined for an IBigdataFederation. It is not possible to define this timestamp without requiring concurrent commit processing to be paused on all data services on which the transaction has written, which is viewed as too high a cost. Instead, the commit timestamp is the state from which you can read the data written by the transaction. Reads on tuples NOT updated by the transaction MAY have been changed by concurrent transactions.

Note: The process of validating, merging down changes, and committing those changes MUST be atomic. Therefore no other operations may be permitted access to the unisolated indices corresponding to the isolated indices on which the transaction during this process. This constraint is generally achieved by holding a write lock on the unisolated indices corresponding to the indices isolated by the transaction, e.g., by declaring those indices to an ITx.UNISOLATED AbstractTask which handles this process.

Author:

Bryan Thompson

Nested Class Summary

Nested classes/interfaces inherited from class com.bigdata.btree.view.FusedView

FusedView.FusedBloomFilter

Field Summary

Fields inherited from class com.bigdata.btree.view.FusedView

ERR_RANGE_COUNT_EXCEEDS_MAX_LONG, log

Fields inherited from interface com.bigdata.btree.IRangeQuery

ALL, CURSOR, DEFAULT, DELETED, FIXED_LENGTH_SUCCESSOR, KEYS, NONE, PARALLEL, READONLY, REMOVEALL, REVERSE, VALS

Constructor Summary

Constructors

Constructor and Description
IsolatedFusedView(long timestamp, AbstractBTree[] sources) Constructor may be used either for a fully isolated transaction or an unisolated operation.

Method Summary

Methods

Modifier and Type	Method and Description
ICounter	getCounter() Counters are disallowed for isolated view.
BTree	getWriteSet() The isolated write set (the place where we record the intention of the transaction).
byte[]	insert(byte[] key, byte[] val) Insert or update a value under the key.
boolean	isEmptyWriteSet() True iff there are no writes on this isolated index.
void	mergeDown(long revisionTime, AbstractBTree[] groundStateSources) Merge the transaction scope index onto the then current unisolated index.
byte[]	putIfAbsent(byte[] key, byte[] val) Insert or update a value under the key iff there is no entry for that key in the index.
byte[]	remove(byte[] key) Write a deleted entry for the key on the write set.
boolean	validate(AbstractBTree[] groundStateSources) Validate changes made to the index within a transaction against the last committed state of the index in the global scope.

Methods inherited from class com.bigdata.btree.view.FusedView

assertNotReadOnly, contains, contains, getBloomFilter, getCounters, getIndexMetadata, getMutableBTree, getResourceMetadata, getSourceCount, getSources, insert, lookup, lookup, lookup, lookup, rangeCount, rangeCount, rangeCountExact, rangeCountExactWithDeleted, rangeIterator, rangeIterator, rangeIterator, remove, submit, submit, submit, toString

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail

IsolatedFusedView

public IsolatedFusedView(long timestamp,
                 AbstractBTree[] sources)

Constructor may be used either for a fully isolated transaction or an unisolated operation. In each case the groundState is the ordered set of read-only resources corresponding to the timestamp.

Reads will read through the writeSet and then the resource(s) in the groundState in the order in which they are given. A read is satisfied by the first resource containing an index entry for the search key.

Writes will first read through looking for a @todo javadoc

Parameters:

timestamp - The timestamp associated with the groundState.

sources - An ordered array of sources comprised of the BTree that will absorb writes and the historical ground state.

Method Detail

getWriteSet

public BTree getWriteSet()

The isolated write set (the place where we record the intention of the transaction). This is just a reference to the mutable BTree at index zero(0) of sources in the view.

See Also:

FusedView.getMutableBTree()

isEmptyWriteSet

public boolean isEmptyWriteSet()

True iff there are no writes on this isolated index.

getCounter

public final ICounter getCounter()

Counters are disallowed for isolated view. The reason is that counters are typically used to create one-up distinct values assigned to keys. If the counter is stored on the write set then different transactions could easily assign the same counter value under different keys, leading to an undetectable write conflict.

Specified by:

getCounter in interface IIndexLocalCounter

Overrides:

getCounter in class FusedView

Throws:

UnsupportedOperationException - always

insert

public byte[] insert(byte[] key,
            byte[] val)

Insert or update a value under the key.

Resolves the old value against the view and then directs the write to the first of the sources specified to the ctor.

Write an entry for the key on the write set.

Specified by:

insert in interface ISimpleBTree

Overrides:

insert in class FusedView

Parameters:

key - The key.

val - The value (may be null).

Returns:

The previous value under that key or null if the key was not found or if the previous entry for that key was marked as deleted.

putIfAbsent

public byte[] putIfAbsent(byte[] key,
                 byte[] val)

Insert or update a value under the key iff there is no entry for that key in the index. This is equivalent to

 if (!contains(key))
        insert(key, value);
 

However, if the index allows null values to be stored under a key and the application in fact stores null values for some tuples, then caller is not able to decide using this method whether or not the mutation was applied based on the return value. For these cases if the caller needs to know whether or not the conditional mutation actually took place, the caller CAN use the pattern if(!contains()) insert(key,value); to obtain that information.

This case is a bit tricky. Since it is possible for the value stored under a key to be null, we need to obtain the Tuple for the key from the view. If the tuple is null or deleted, then we can do an unconditional insert. Otherwise there is an entry under the key and we return the value of the entry from the Tuple. Note that the value COULD be a null.

Write an entry for the key on the write set.

Specified by:

putIfAbsent in interface ISimpleBTree

Overrides:

putIfAbsent in class FusedView

Parameters:

key - The key.

val - The value (may be null).

Returns:

The previous value under that key or null if the key was not found or if the previous entry for that key was marked as deleted. Note that the return value MAY be null even if there was an entry under the key. This is because the index is capable of storing a null value. In such cases the conditional mutation WAS NOT applied.

See Also:

(putIfAbsent)

remove

public byte[] remove(byte[] key)

Write a deleted entry for the key on the write set.

Specified by:

remove in interface ISimpleBTree

Overrides:

remove in class FusedView

Parameters:

key - The key.

Returns:

The value stored under that key or null if the key was not found or if the previous entry under that key was marked as deleted.

validate

public boolean validate(AbstractBTree[] groundStateSources)

Validate changes made to the index within a transaction against the last committed state of the index in the global scope. In general there are two kinds of conflicts: read-write conflicts and write-write conflicts. Read-write conflicts are handled by NEVER overwriting an existing version (an MVCC style strategy). Write-write conflicts are detected by backward validation against the last committed state of the journal. A write-write conflict exists IFF the version counter on the transaction index entry differs from the version counter in the global index scope. Once detected, the resolution of a write-write conflict is delegated to a conflict resolver. If a write-write conflict can not be validated, then validation will fail and the transaction must abort.

Validation occurs as part of the prepare/commit protocol. Concurrent transactions MAY continue to run without limitation. A concurrent commit (if permitted) would force re-validation since the transaction MUST now be validated against the new baseline. (It is possible that this validation could be optimized.)

The version counters used to detect write-write conflicts are incremented during the commit as part of the #mergeDown() of the IsolatedFusedView onto the corresponding unisolated indices in the global scope.

Parameters:

groundStateSources - The ordered view of the unisolated index. This MUST be the current view of the ground state as of when the transaction is validated (NOT when it was created). This view WILL NOT the same as the groundState specified to the constructor if intervening transactions have committed on the index.

Returns:

True iff validation succeeds.

mergeDown

public void mergeDown(long revisionTime,
             AbstractBTree[] groundStateSources)

Merge the transaction scope index onto the then current unisolated index.

Note: This method is invoked by a transaction during commit processing to merge the write set of an IsolatedFusedView into the global scope. This operation does NOT check for conflicts. The pre-condition is that the transaction has already been validated (hence, there will be no conflicts).

Note: This method is also responsible for updating the version timestamps that are used to detect write-write conflicts during validation - they are set to the revisionTime.

Parameters:

revisionTime - The revision timestamp assigned to the commit point of the transaction.

groundStateSources - The ordered view of the unisolated index. This MUST be the current view of the ground state as of when the transaction is validated (NOT when it was created). This view WILL NOT the same as the groundState specified to the constructor if intervening transactions have committed on the index.