com.bigdata.counters.store
Class CounterSetBTree

java.lang.Object
  com.bigdata.btree.AbstractBTree
      com.bigdata.btree.BTree
          com.bigdata.counters.store.CounterSetBTree

All Implemented Interfaces:

IAutoboxBTree, IBTreeStatistics, ICheckpointProtocol, IIndex, IIndexLocalCounter, ILinearList, ILocalBTreeView, IRangeQuery, ISimpleBTree, ICounterSetAccess, ICommitter

public class CounterSetBTree
extends BTree

An API encapsulating for writing and querying counter sets. The data are written onto an IIndex. The IIndex may be local or remote.

The multipart key is used. The first component is the milliseconds of the associated timestamp value rounded down to an even number of minutes and represented a long. The second component is the fully qualified path of the counter. The last component is the exact timestamp (in milliseconds) of the sampled counter value, represented as a long. These are formatted into an unsigned byte[] following the standard practice.

The value stored under the key is the counter value. Normally counter values are doubles or longs, but you can store any of the counter value types which are supported by the SparseRowStore.

Using this approach, writes of the same counter value with different timestamps will be recorded as different tuples in the IIndex and you can store counter values sampled at rates of once per second while retaining good compression for the keys in the index.

Version:

$Id: CounterSetBTree.java 4882 2011-07-10 17:47:23Z thompsonbry $ FIXME Reading through per-minute counters from a CounterSetBTree grows slow very quickly.

 There are 21750988 counter values covering Fri Apr 03 15:51:57 EDT 2009 to
 Sat Apr 04 08:45:05 EDT 2009. Took 60 seconds to record each hour of data on
 the disk.  1.2G of XML data expanded to 2.6G on the journal
 

In order to improve performance, put the counter paths in a separate dictionary and apply the regex there. Once we have the set of matched paths we can scatter range queries against the BTree and drag back the data for those counters (this would also make Unicode counter names viable). If the key was then [pathId,timestamp] we could do ordered reads of just the necessary key range for each desired counter. Prefix compression would still be efficent for this representation. While the data arrive in history blocks, we would still need to buffer them for ordered writes since otherwise the writes would be scattered by the first key component (pathId).

I would have to encapsulate the counters as a counter for this to work, much like the RDF DB. There would be two relations: the dictionary and the timestamped values.

Space efficient encoding of the counter values would also help quite a bit - it is Java default serialization, but we only store Long, Double or String. All values for a given counter should have the same data type (it is required by how we allocate the History) so the data type can be part of the dictionary and that can be used to decode the value. (If values tend to be close then a delta encoding would help.)

Author:

Bryan Thompson

Nested Class Summary

protected static class	CounterSetBTree.CounterSetBTreeTupleSerializer Encapsulates key and value formation.
static class	CounterSetBTree.Entry A representation of a timestamped performance counter value as stored in the CounterSetBTree.

Nested classes/interfaces inherited from class com.bigdata.btree.BTree

BTree.Counter, BTree.LeafCursor, BTree.NodeFactory, BTree.PartitionedCounter, BTree.Stack

Nested classes/interfaces inherited from class com.bigdata.btree.AbstractBTree

AbstractBTree.IBTreeCounters

Field Summary

protected static org.apache.log4j.Logger

log

Fields inherited from class com.bigdata.btree.BTree

counter, height, nentries, nleaves, nnodes, recordVersion

Fields inherited from class com.bigdata.btree.AbstractBTree

branchingFactor, debug, DEBUG, dumpLog, ERROR_CLOSED, ERROR_LESS_THAN_ZERO, ERROR_READ_ONLY, ERROR_TOO_LARGE, ERROR_TRANSIENT, INFO, metadata, ndistinctOnWriteRetentionQueue, nodeSer, readOnly, root, store, storeCache, writeRetentionQueue

Fields inherited from interface com.bigdata.btree.IRangeQuery

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

Constructor Summary

CounterSetBTree(IRawStore store, Checkpoint checkpoint, IndexMetadata metadata, boolean readOnly)

Method Summary

static CounterSetBTree	create(IRawStore store) Create a new instance.
static CounterSetBTree	createTransient()
long	getFirstTimestamp() Return the timestamp associated with the first performance counter value.
long	getLastTimestamp() Return the timestamp associated with the last performance counter value.
CounterSet	rangeIterator(long fromTime, long toTime, TimeUnit unit, Pattern filter, int depth) The toTime needs to be ONE (1) unit beyond the time of interest since the minutes come first in the key.
void	writeCurrent(Iterator<ICounter> src) Writes the current value of each visited ICounter on the store.
void	writeHistory(Iterator<ICounter> src) Handles efficient writes of counters with History data.

Methods inherited from class com.bigdata.btree.BTree

_reopen, asReadOnly, create, createTransient, createViewCheckpoint, fireDirtyEvent, getBloomFilter, getCheckpoint, getCounter, getDirtyListener, getEntryCount, getHeight, getLastCommitTime, getLeafCount, getMetadataAddr, getMutableBTree, getNodeCount, getRecordVersion, getRevisionTimestamp, getRootAddr, getSourceCount, getSources, getStore, handleCommit, load, load, needsCheckpoint, newLeafCursor, newLeafCursor, readBloomFilter, removeAll, setDirtyListener, setIndexMetadata, setLastCommitTime, writeCheckpoint, writeCheckpoint2

Methods inherited from class com.bigdata.btree.AbstractBTree

assertNotReadOnly, assertNotTransient, close, contains, contains, decodeRecordAddr, dump, dump, encodeRecordAddr, getBranchingFactor, getBtreeCounters, getContainsTuple, getCounters, getIndexMetadata, getLookupTuple, getNodeSerializer, getResourceMetadata, getRightMostNode, getRoot, getRootOrFinger, getStatistics, getUtilization, getWriteTuple, indexOf, insert, insert, insert, isOpen, isReadOnly, isTransient, keyAt, lookup, lookup, lookup, rangeCheck, rangeCopy, rangeCount, rangeCount, rangeCount, rangeCountExact, rangeCountExactWithDeleted, rangeIterator, rangeIterator, rangeIterator, rangeIterator, rangeIterator, readNodeOrLeaf, recycle, remove, remove, remove, reopen, setBTreeCounters, submit, submit, submit, toString, touch, valueAt, valueAt, writeNodeOrLeaf, writeNodeRecursive

Methods inherited from class java.lang.Object

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

Field Detail

log

protected static final transient org.apache.log4j.Logger log

Constructor Detail

CounterSetBTree

public CounterSetBTree(IRawStore store,
                       Checkpoint checkpoint,
                       IndexMetadata metadata,
                       boolean readOnly)

Parameters:

store -

checkpoint -

metadata -

Method Detail

create

public static CounterSetBTree create(IRawStore store)

Create a new instance.

Parameters:

store - The backing store.

Returns:

The new instance.

createTransient

public static CounterSetBTree createTransient()

writeHistory

public void writeHistory(Iterator<ICounter> src)

Handles efficient writes of counters with History data. The shape of the data is changed so that the resulting writes on the BTree will be ordered. This is both faster and also results in a smaller size on the size (since leaves are not updated once they are written to the store). For a counter without history, the current value of the counter will be written on the BTree.

writeCurrent

public void writeCurrent(Iterator<ICounter> src)

Writes the current value of each visited ICounter on the store.

Note: This presumes that the counters are associated with scalar values (rather than Historys).

Note that the counter set iterator will normally be in alpha order already and all samples should be close to the same minute, so this is already efficient for local operations.

TODO:

More efficient storage for Double, Long, Integer and String values (this is using Java default serialization)?

rangeIterator

public CounterSet rangeIterator(long fromTime,
                                long toTime,
                                TimeUnit unit,
                                Pattern filter,
                                int depth)

The toTime needs to be ONE (1) unit beyond the time of interest since the minutes come first in the key. If you do not follow this rule then you can miss out on the last unit worth of data.

Parameters:

fromTime - The first time whose counters will be visited (in milliseconds).

toTime - The first time whose counters WILL NOT be visited (in milliseconds).

unit - The unit of aggregation for the reported counters.

filter - Only paths matched by the filter will be accepted (optional).

depth - When non-zero, only counters whose depth is LTE to the specified depth will be returned.

Returns:

A collection of the selected performance counters together with their ordered timestamped values for the specified time period.

TODO:

In an act of cowardice, this assumes that the counter paths are ASCII and encodes them as such. This allows us to decode the counter path since it is not a compressed sort key. If we don't take this "hack" then we need a 2nd index to resolve the Unicode path from the sort key (once we hack off the leading minutes component).

The other problem is that tacking the milliseconds onto the end of the key might break the natural order of the counter paths in the index.

The two index approach is not so bad. The main drawback is that it can't be encapsulated as easily.

getFirstTimestamp

public long getFirstTimestamp()

Return the timestamp associated with the first performance counter value.

Returns:

The timestamp -or- 0L if there are no performance counter values.

getLastTimestamp

public long getLastTimestamp()

Return the timestamp associated with the last performance counter value.

Returns:

The timestamp -or- 0L if there are no performance counter values.