public class FusedView extends Object implements IIndex, ILocalBTreeView
A fused view providing read-write operations on multiple B+-Trees mapping variable length unsigned byte[] keys to arbitrary values. The sources MUST support deletion markers. The order of the sources MUST correspond to the recency of their data. Writes will be directed to the first source in the sequence (the most recent source). Deletion markers are used to prevent a miss on a key for a source from reading through to an older source. If a deletion marker is encountered the index entry will be understood as "not found" in the fused view rather than reading through to an older source where it might still have a binding.
| Modifier and Type | Class and Description |
|---|---|
protected class |
FusedView.FusedBloomFilter
Inner class providing a fused view of the optional bloom filters
associated with each of the source indices.
|
| Modifier and Type | Field and Description |
|---|---|
protected static String |
ERR_RANGE_COUNT_EXCEEDS_MAX_LONG
Error message if the view has more than
Long.MAX_VALUE elements
and you requested an exact range count. |
protected static org.apache.log4j.Logger |
log |
| Constructor and Description |
|---|
FusedView(AbstractBTree[] srcs) |
FusedView(AbstractBTree src1,
AbstractBTree src2) |
| Modifier and Type | Method and Description |
|---|---|
protected void |
assertNotReadOnly() |
boolean |
contains(byte[] key)
Return
true iff there is a (non-deleted) index entry for
the key. |
boolean |
contains(Object key)
Return true iff there is an entry for the key.
|
IBloomFilter |
getBloomFilter()
Return the bloom filter.
|
ICounter |
getCounter()
The counter for the first source.
|
CounterSet |
getCounters()
Return performance counters.
|
IndexMetadata |
getIndexMetadata()
The metadata for the index.
|
BTree |
getMutableBTree()
The
BTree that is absorbing writes for the view. |
IResourceMetadata[] |
getResourceMetadata()
The description of the resources comprising the index view.
|
int |
getSourceCount()
The #of
AbstractBTrees sources for the view. |
AbstractBTree[] |
getSources()
An array containing the ordered sources in the view.
|
byte[] |
insert(byte[] key,
byte[] value)
Insert or update a value under the key.
|
Object |
insert(Object key,
Object val)
Insert with auto-magic handling of keys and value objects.
|
byte[] |
lookup(byte[] key)
Lookup a value for a key.
|
Tuple |
lookup(byte[] key,
Tuple tuple)
Per
AbstractBTree.lookup(byte[], Tuple) but0 processes the
AbstractBTrees in the view in their declared sequence and stops
when it finds the first index entry for the key, even it the entry is
marked as deleted for that key. |
protected Tuple |
lookup(int startIndex,
byte[] key,
Tuple tuple)
Core implementation processes the
AbstractBTrees in the view in
their declared sequence and stops when it finds the first index entry for
the key, even it the entry is marked as deleted for that key. |
Object |
lookup(Object key)
Lookup a value for a key.
|
byte[] |
putIfAbsent(byte[] key,
byte[] value)
Insert or update a value under the key iff there is no entry for that key
in the index.
|
long |
rangeCount()
Return the #of tuples in the index.
|
long |
rangeCount(byte[] fromKey,
byte[] toKey)
Return the #of tuples in a half-open key range.
|
long |
rangeCountExact(byte[] fromKey,
byte[] toKey)
Return the exact #of tuples in a half-open key range.
|
long |
rangeCountExactWithDeleted(byte[] fromKey,
byte[] toKey)
Return the exact #of tuples in a half-open key range, including any
deleted tuples.
|
ITupleIterator |
rangeIterator()
Visits all tuples in key order.
|
ITupleIterator |
rangeIterator(byte[] fromKey,
byte[] toKey)
Return an iterator that visits the entries in a half-open key range.
|
ITupleIterator |
rangeIterator(byte[] fromKey,
byte[] toKey,
int capacity,
int flags,
IFilter filter)
Core implementation.
|
byte[] |
remove(byte[] key)
Resolves the old value against the view and then directs the write to the
first of the sources specified to the ctor.
|
Object |
remove(Object key)
Remove the key and its associated value.
|
void |
submit(byte[] fromKey,
byte[] toKey,
IKeyRangeIndexProcedure proc,
IResultHandler handler)
The procedure will be transparently applied against each index partition
spanned by the given key range.
|
<T> T |
submit(byte[] key,
ISimpleIndexProcedure<T> proc)
Submits an index procedure that operations on a single key to the
appropriate index partition returning the result of that procedure.
|
void |
submit(int fromIndex,
int toIndex,
byte[][] keys,
byte[][] vals,
AbstractKeyArrayIndexProcedureConstructor ctor,
IResultHandler aggregator)
Runs a procedure against an index.
|
String |
toString() |
protected static final org.apache.log4j.Logger log
protected static final transient String ERR_RANGE_COUNT_EXCEEDS_MAX_LONG
Long.MAX_VALUE elements
and you requested an exact range count.public FusedView(AbstractBTree src1, AbstractBTree src2)
public FusedView(AbstractBTree[] srcs)
srcs - The ordered sources for the fused view. The order of the
elements in this array determines which value will be selected
for a given key by lookup() and which value is retained by
rangeQuery().IllegalArgumentException - if a source is used more than once.IllegalArgumentException - unless all sources have the same indexUUIDIllegalArgumentException - unless all sources support delete markers.public final AbstractBTree[] getSources()
ILocalBTreeViewAbstractBTree then the
array will contain a single element which is that AbstractBTree.getSources in interface ILocalBTreeViewpublic final int getSourceCount()
ILocalBTreeViewAbstractBTrees sources for the view. This will be ONE (1)
if the view is a BTree.getSourceCount in interface ILocalBTreeViewpublic final BTree getMutableBTree()
ILocalBTreeViewBTree that is absorbing writes for the view.getMutableBTree in interface ILocalBTreeViewprotected void assertNotReadOnly()
public IResourceMetadata[] getResourceMetadata()
IIndexgetResourceMetadata in interface IIndexpublic IndexMetadata getIndexMetadata()
IIndex
Note: The same method is exposed by ICheckpointProtocol. It is
also exposed here in order to provide access to the IndexMetadata
to remote clients in the scale-out architecture.
getIndexMetadata in interface IIndexICheckpointProtocol.getIndexMetadata()public IBloomFilter getBloomFilter()
ILocalBTreeViewgetBloomFilter in interface ILocalBTreeViewnull.public final CounterSet getCounters()
IIndexInteresting performance counters and other statistics about the index.
getCounters in interface IIndexgetCounters in interface ICounterSetAccesspublic ICounter getCounter()
getCounter in interface IIndexLocalCounterpublic byte[] insert(byte[] key,
byte[] value)
Resolves the old value against the view and then directs the write to the first of the sources specified to the ctor.
insert in interface ISimpleBTreekey - The key.value - The value (may be null).null if the
key was not found or if the previous entry for that key was
marked as deleted.public byte[] putIfAbsent(byte[] key,
byte[] value)
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.
putIfAbsent in interface ISimpleBTreekey - The key.value - The value (may be null).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.(putIfAbsent)public Object insert(Object key, Object val)
IAutoboxBTreeinsert in interface IAutoboxBTreekey - The key is implicitly converted to an unsigned
byte[].val - The value is implicitly converted to a byte[].null if there was
no value stored under that key.public byte[] remove(byte[] key)
remove in interface ISimpleBTreekey - The key.null if the key
was not found or if the previous entry under that key was marked
as deleted.public Object remove(Object key)
IAutoboxBTreeremove in interface IAutoboxBTreekey - The key is implicitly converted to an unsigned
byte[].null if the key was not found.public final byte[] lookup(byte[] key)
Return the first value for the key in an ordered search of the trees in the view.
lookup in interface ISimpleBTreenull if there
is no entry for that key or if the entry under that key is marked
as deleted.public Object lookup(Object key)
IAutoboxBTreelookup in interface IAutoboxBTreekey - The key is implicitly converted to an unsigned
byte[].null if there is no
entry for that key.public final Tuple lookup(byte[] key, Tuple tuple)
AbstractBTree.lookup(byte[], Tuple) but0 processes the
AbstractBTrees in the view in their declared sequence and stops
when it finds the first index entry for the key, even it the entry is
marked as deleted for that key.key - The search key.tuple - A tuple to be populated with data and metadata about the index
entry (required).protected final Tuple lookup(int startIndex, byte[] key, Tuple tuple)
AbstractBTrees in the view in
their declared sequence and stops when it finds the first index entry for
the key, even it the entry is marked as deleted for that key.startIndex - The index of the first source to be read. This permits the
lookup operation to start at an index into the #srcs
other than zero. This is used by IsolatedFusedView to
read from just the groundState (everything except the
writeSet, which is the source at index zero(0)).key - The search key.tuple - A tuple to be populated with data and metadata about the index
entry (required).public final boolean contains(byte[] key)
true iff there is a (non-deleted) index entry for
the key. An index entry with a null value will cause this
method to return true. A deleted index entry will cause
this method to return false.
Processes the AbstractBTrees in the view in sequence and returns
true iff the first AbstractBTree with an index entry under the
key is non-deleted.
contains in interface ISimpleBTreekey - The key.true if the index contains an (un-deleted) entry
for that key.public boolean contains(Object key)
IAutoboxBTreecontains in interface IAutoboxBTreekey - The key is implicitly converted to an unsigned
byte[].public final long rangeCount()
Note: If the index supports deletion markers then the range count will be an upper bound and may double count tuples which have been overwritten, including the special case where the overwrite is a delete.
Returns the sum of the range count on each index in the view. This is the maximum #of entries that could lie within that key range. However, the actual number could be less if there are entries for the same key in more than one source index.
rangeCount in interface IRangeQueryISimpleIndexAccess.rangeCount()public final long rangeCount(byte[] fromKey,
byte[] toKey)
Note: If the index supports deletion markers then the range count will be an upper bound and may double count tuples which have been overwritten, including the special case where the overwrite is a delete.
Returns the sum of the range count on each index in the view. This is the maximum #of entries that could lie within that key range. However, the actual number could be less if there are entries for the same key in more than one source index.
rangeCount in interface IRangeQueryfromKey - The lowest key that will be counted (inclusive). When
null there is no lower bound.toKey - The first key that will not be counted (exclusive). When
null there is no upper bound.public final long rangeCountExact(byte[] fromKey,
byte[] toKey)
Note: If the index supports deletion markers then this operation will require a key-range scan.
The exact range count is obtained using a key-range scan over the view.
rangeCountExact in interface IRangeQueryfromKey - The lowest key that will be counted (inclusive). When
null there is no lower bound.toKey - The first key that will not be counted (exclusive). When
null there is no upper bound.public long rangeCountExactWithDeleted(byte[] fromKey,
byte[] toKey)
When the view is just an AbstractBTree the result is the same as
for IRangeQuery.rangeCount(byte[], byte[]), which already
reports all tuples regardless of whether or not they are deleted.
When the index is a view with multiple sources, this operation requires a key-range scan where both deleted and undeleted tuples are visited.
An exact range count that includes any deleted tuples. This is obtained using a key-range scan over the view.
rangeCountExactWithDeleted in interface IRangeQueryfromKey - The lowest key that will be counted (inclusive). When
null there is no lower bound.toKey - The first key that will not be counted (exclusive). When
null there is no upper bound.rangeCountExact(byte[], byte[])public ITupleIterator rangeIterator()
IRangeQueryrangeIterator(null, null)
rangeIterator in interface IRangeQuerypublic final ITupleIterator rangeIterator(byte[] fromKey, byte[] toKey)
Returns an iterator that visits the distinct entries. When an entry appears in more than one index, the entry is chosen based on the order in which the indices were declared to the constructor.
rangeIterator in interface IRangeQueryfromKey - The first key that will be visited (inclusive lower bound).
When null there is no lower bound.toKey - The first key that will NOT be visited (exclusive upper
bound). When null there is no upper bound.SuccessorUtil, which may be used to compute the successor of a value
before encoding it as a component of a key.,
BytesUtil#successor(byte[]), which may be used to compute the
successor of an encoded key.,
EntryFilter, which may be used to filter the entries visited by the
iterator.public ITupleIterator rangeIterator(byte[] fromKey, byte[] toKey, int capacity, int flags, IFilter filter)
Core implementation.
Note: The FusedView's iterator first obtains an ordered array of
iterators for each of the source AbstractBTrees. The filter
is NOT passed through to these source iterators. Instead, an
FusedTupleIterator is obtained and the filter is applied to that
iterator. This means that filters always see a fused representation of
the source iterators.
Note: This implementation supports IRangeQuery.REVERSE. This may
be used to locate the ITuple before a specified key, which is a
requirement for several aspects of the overall architecture including
atomic append of file blocks, locating an index partition in the metadata
index, and finding the last member of a set or map.
Note: When the IRangeQuery.CURSOR flag is specified, it is passed
through and an ITupleCursor is obtained for each source
AbstractBTree. A FusedTupleCursor is then obtained which
implements the ITupleCursor extensions.
rangeIterator in interface IRangeQueryfromKey - The first key that will be visited (inclusive lower bound).
When null there is no lower bound.toKey - The first key that will NOT be visited (exclusive upper
bound). When null there is no upper bound.capacity - The #of entries to buffer at a time. This is a hint and MAY be
zero (0) to use an implementation specific default
capacity. A non-zero value may be used if you know that you
want at most N results or if you want to override the default
#of results to be buffered before sending them across a
network interface. (Note that you can control the default
value using
IBigdataClient.Options#DEFAULT_CLIENT_RANGE_QUERY_CAPACITY).flags - A bitwise OR of IRangeQuery.KEYS, IRangeQuery.VALS, etc.filter - An optional object used to construct a stacked iterator. When
IRangeQuery.CURSOR is specified in flags, the base
iterator will implement ITupleCursor and the first
filter in the stack can safely cast the source iterator to an
ITupleCursor. If the outermost filter in the stack
does not implement ITupleIterator, then it will be
wrapped an ITupleIterator.SuccessorUtil, which may be used to compute the successor of a value
before encoding it as a component of a key.,
BytesUtil#successor(byte[]), which may be used to compute the
successor of an encoded key.,
IFilterConstructor, which may be used to construct an iterator stack
performing filtering or other operations.public final <T> T submit(byte[] key,
ISimpleIndexProcedure<T> proc)
IIndexsubmit in interface IIndexkey - The key.proc - The procedure.IIndexProcedure.apply(IIndex)public final void submit(byte[] fromKey,
byte[] toKey,
IKeyRangeIndexProcedure proc,
IResultHandler handler)
IIndex
Note: Since this variant of submit() does not split keys the
fromIndex and toIndex in the Splits reported to
the IResultHandler will be zero (0).
submit in interface IIndexfromKey - The lower bound (inclusive) -or- null if there
is no lower bound.toKey - The upper bound (exclusive) -or- null if there
is no upper bound.proc - The procedure. If the procedure implements the
IParallelizableIndexProcedure marker interface then it
MAY be executed in parallel against the relevant index
partition(s).public void submit(int fromIndex,
int toIndex,
byte[][] keys,
byte[][] vals,
AbstractKeyArrayIndexProcedureConstructor ctor,
IResultHandler aggregator)
IIndex
Note: This may be used to send custom logic together with the data to a
remote index or index partition. When the index is remote both the
procedure and the return value MUST be Serializable.
Note: The scale-out indices add support for auto-split of the procedure such that it runs locally against each relevant index partition.
submit in interface IIndexfromIndex - The index of the first key to be used (inclusive).toIndex - The index of the last key to be used (exclusive).keys - The keys (required).vals - The values (optional depending on the procedure).ctor - An object that can create instances of the procedure.aggregator - When defined, results from each procedure application will be
reported to this object.
TODO In order to allow parallelization within a shard, we need to modify
this method signature to pass in an IResultHandler constructor
object. That might be something which could be pushed down onto the ctor
argument. It would be used in scale-out to create a DS local result handler
so we can locally aggregate when parallelizing against each shard and then
return that aggregated result to the client which would extract the aggregate
result across the shards from the client's result handler. See BLZG-1537.(Schedule more IOs when loading data)Copyright © 2006–2019 SYSTAP, LLC DBA Blazegraph. All rights reserved.