net.opentsdb.tree

Class Branch

java.lang.Object

net.opentsdb.tree.Branch

All Implemented Interfaces:

Comparable<Branch>

public final class Branch
extends Object
implements Comparable<Branch>

Represents a branch of a meta data tree, used to organize timeseries into a hierarchy for easy navigation. Each branch is composed of itself and potential child branches and/or child leaves.

Branch IDs are hex encoded byte arrays composed of the tree ID + hash of the display name for each previous branch. The tree ID is encoded on Tree.TREE_ID_WIDTH() bytes, each hash is then INT_WIDTH bytes. So the if the tree ID width is 2 bytes and Java Integers are 4 bytes, the root for tree # 1 is just 0001. A child of the root could be 00001A3B190C2 and so on. These IDs are used as the row key in storage.

Branch definitions are JSON objects stored in the "branch" column of the branch ID row. Only the tree ID, path and display name are stored in the definition column to keep space down. Leaves are stored in separate columns and child branch definitions are stored in separate rows. Note that the root branch definition for a tree will be stored in the same row as the tree definition since they share the same row key.

When fetching a branch with children and leaves, a scanner is configured with a row key regex to scan any rows that match the branch ID plus an additional INT_WIDTH so that when we scan, we can pick up all of the rows with child branch definitions. Also, when loading a full branch, any leaves for the request branch can load the associated UID names from storage, so this can get expensive. Leaves for a child branch will not be loaded, only leaves that belong directly to the local will. Also, children branches of children will not be loaded. We only return one branch at a time since the tree could be HUGE!

Storing a branch will only write the definition column for the local branch object. Child branches will not be written to storage. If you've loaded and modified children in this branch, you need to loop through the children and store them individually. Leaves belonging to this branch will be stored and collisions recorded to the given Tree object.

Since:

2.0

Constructor Summary

Constructors

Constructor and Description
Branch() Default empty constructor necessary for de/serialization
Branch(Branch original) Copy constructor that creates a completely independent copy of the original
Branch(int tree_id) Constructor that sets the tree ID

Method Summary

Methods

Modifier and Type	Method and Description
boolean	addChild(Branch branch) Adds a child branch to the local branch set if it doesn't exist.
boolean	addLeaf(Leaf leaf, Tree tree) Adds a leaf to the local branch, looking for collisions
static byte[]	BRANCH_QUALIFIER()
int	compareTo(Branch branch) Comparator based on the display_name to sort branches when returning to an RPC calls
byte[]	compileBranchId() Attempts to compile the branch ID for this branch.
boolean	equals(Object obj) Just compares the branch display name
static com.stumbleupon.async.Deferred<Branch>	fetchBranch(TSDB tsdb, byte[] branch_id, boolean load_leaf_uids) Attempts to fetch the branch, it's leaves and all child branches.
static com.stumbleupon.async.Deferred<Branch>	fetchBranchOnly(TSDB tsdb, byte[] branch_id) Attempts to fetch only the branch definition object from storage.
TreeSet<Branch>	getBranches()
String	getBranchId()
int	getDepth()
String	getDisplayName()
TreeSet<Leaf>	getLeaves()
Map<Integer,String>	getPath()
int	getTreeId()
int	hashCode()
static String	idToString(byte[] branch_id) Converts a branch ID hash to a hex encoded, upper case string with padding
void	prependParentPath(Map<Integer,String> parent_path) Sets the path for this branch based off the path of the parent.
void	setDisplayName(String display_name)
void	setTreeId(int tree_id)
com.stumbleupon.async.Deferred<ArrayList<Boolean>>	storeBranch(TSDB tsdb, Tree tree, boolean store_leaves) Attempts to write the branch definition and optionally child leaves to storage via CompareAndSets.
static byte[]	stringToId(String branch_id) Converts a hex string to a branch ID byte array (row key)
String	toString()

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Constructor Detail

Branch

public Branch()

Default empty constructor necessary for de/serialization

Branch

public Branch(int tree_id)

Constructor that sets the tree ID

Parameters:

tree_id - ID of the tree this branch is associated with

Branch

public Branch(Branch original)

Copy constructor that creates a completely independent copy of the original

Parameters:

original - The original object to copy from

Method Detail

hashCode

public int hashCode()

Overrides:

hashCode in class Object

Returns:

Returns the display_name's hash code or 0 if it's not set

equals

public boolean equals(Object obj)

Just compares the branch display name

Overrides:

equals in class Object

Parameters:

obj - The object to compare this to

Returns:

True if the branch IDs are the same or the incoming object is this one

compareTo

public int compareTo(Branch branch)

Comparator based on the display_name to sort branches when returning to an RPC calls

Specified by:

compareTo in interface Comparable<Branch>

toString

public String toString()

Overrides:

toString in class Object

Returns:

Information about this branch including ID and display name

addChild

public boolean addChild(Branch branch)

Adds a child branch to the local branch set if it doesn't exist. Also initializes the set if it hasn't been initialized yet

Parameters:

branch - The branch to add

Returns:

True if the branch did not exist in the set previously

Throws:

IllegalArgumentException - if the incoming branch is null

addLeaf

public boolean addLeaf(Leaf leaf,
              Tree tree)

Adds a leaf to the local branch, looking for collisions

Parameters:

leaf - The leaf to add

tree - The tree to report to with collisions

Returns:

True if the leaf was new, false if the leaf already exists or would cause a collision

Throws:

IllegalArgumentException - if the incoming leaf is null

compileBranchId

public byte[] compileBranchId()

Attempts to compile the branch ID for this branch. In order to successfully compile, the tree_id, path and display_name must be set. The path may be empty, which indicates this is a root branch, but it must be a valid Map object.

Returns:

The branch ID as a byte array

Throws:

IllegalArgumentException - if any required parameters are missing

prependParentPath

public void prependParentPath(Map<Integer,String> parent_path)

Sets the path for this branch based off the path of the parent. This map may be empty, in which case the branch is considered a root. Warning: If the path has already been set, this will create a new path, clearing out any existing entries

Parameters:

parent_path - The map to store as the path

Throws:

IllegalArgumentException - if the parent path is null

storeBranch

public com.stumbleupon.async.Deferred<ArrayList<Boolean>> storeBranch(TSDB tsdb,
                                                             Tree tree,
                                                             boolean store_leaves)

Attempts to write the branch definition and optionally child leaves to storage via CompareAndSets. Each returned deferred will be a boolean regarding whether the CAS call was successful or not. This will be a mix of the branch call and leaves. Some of these may be false, which is OK, because if the branch definition already exists, we don't need to re-write it. Leaves will return false if there was a collision.

Parameters:

tsdb - The TSDB to use for access

tree - The tree to record collisions to

store_leaves - Whether or not child leaves should be written to storage

Returns:

A list of deferreds to wait on for completion.

Throws:

org.hbase.async.HBaseException - if there was an issue

IllegalArgumentException - if the tree ID was missing or data was missing

fetchBranchOnly

public static com.stumbleupon.async.Deferred<Branch> fetchBranchOnly(TSDB tsdb,
                                                     byte[] branch_id)

Attempts to fetch only the branch definition object from storage. This is much faster than scanning many rows for child branches as per the fetchBranch(net.opentsdb.core.TSDB, byte[], boolean) call. Useful when building trees, particularly to fetch the root branch.

Parameters:

tsdb - The TSDB to use for access

branch_id - ID of the branch to retrieve

Returns:

A branch if found, null if it did not exist

Throws:

JSONException - if the object could not be deserialized

fetchBranch

public static com.stumbleupon.async.Deferred<Branch> fetchBranch(TSDB tsdb,
                                                 byte[] branch_id,
                                                 boolean load_leaf_uids)

Attempts to fetch the branch, it's leaves and all child branches. The UID names for each leaf may also be loaded if configured.

Parameters:

tsdb - The TSDB to use for storage access

branch_id - ID of the branch to retrieve

load_leaf_uids - Whether or not to load UID names for each leaf

Returns:

A branch if found, null if it did not exist

Throws:

JSONException - if the object could not be deserialized

idToString

public static String idToString(byte[] branch_id)

Converts a branch ID hash to a hex encoded, upper case string with padding

Parameters:

branch_id - The ID to convert

Returns:

the branch ID as a character hex string

stringToId

public static byte[] stringToId(String branch_id)

Converts a hex string to a branch ID byte array (row key)

Parameters:

branch_id - The branch ID to convert

Returns:

The branch ID as a byte array

Throws:

IllegalArgumentException - if the string is not valid hex

BRANCH_QUALIFIER

public static byte[] BRANCH_QUALIFIER()

Returns:

The branch column qualifier name

getTreeId

public int getTreeId()

Returns:

The ID of the tree this branch belongs to

getBranchId

public String getBranchId()

Returns:

The ID of this branch

getPath

public Map<Integer,String> getPath()

Returns:

The path of the tree

getDepth

public int getDepth()

Returns:

Depth of this branch

getDisplayName

public String getDisplayName()

Returns:

Name to display to the public

getLeaves

public TreeSet<Leaf> getLeaves()

Returns:

Ordered set of leaves belonging to this branch

getBranches

public TreeSet<Branch> getBranches()

Returns:

Ordered set of child branches

setTreeId

public void setTreeId(int tree_id)

Parameters:

tree_id - ID of the tree this branch belongs to

setDisplayName

public void setDisplayName(String display_name)

Parameters:

display_name - Public name to display