ostore.apps.qtree.impl
Class QTree

java.lang.Object
  |
  +--ostore.util.StandardStage
        |
        +--ostore.apps.qtree.impl.QTree

All Implemented Interfaces:

EventHandlerIF, ProfilableIF, SingleThreadedEventHandlerIF

public class QTree

extends StandardStage

implements SingleThreadedEventHandlerIF, ProfilableIF

This stage creates and maintains a distributed query tree. Queries are multicasted to every participating node, and results are collected at the declared root of the tree. Applications include: Visualization (Sonar), Availability, All-Pairs-Ping, Dhtb tests, etc.

Version:

$Id: QTree.java,v 1.18 2004/05/13 19:42:08 hweather Exp $

Author:

Jason Lee

Nested Class Summary

protected class	QTree.ChildrenEvent
protected class	QTree.DeadParent
protected class	QTree.EvalPotParents
protected class	QTree.ParentEvent
protected class	QTree.ProcessCache

Field Summary

static int	CLOSED
protected int	NUM_RETRIES
static int	OPENING
static int	STABLE
protected long	TIMEOUT_ACK
protected long	TIMEOUT_ADOPT
protected long	TIMEOUT_DELAY
protected long	TIMEOUT_MSG

Fields inherited from class ostore.util.StandardStage

classifier, DEBUG, event_types, inb_msg_types, logger, my_node_id, my_sink, outb_msg_types, resender, resender_tokens, serializable_types, sim_running, tag

Constructor Summary

QTree()

Method Summary

protected void	alterState(QTreeStateMsg msg) Only root receives a QTreeStateMsg.
protected void	chooseParent(QTree.EvalPotParents event)
protected void	closeChild(TreeKey key, NodeId node)
protected void	closeParent(TreeKey key, NodeId node)
protected void	considerAdoption(QTreeGroupMsg msg)
protected boolean	contactCandidateOrphan(GuidAddr node, TreeKey treeKey, int level, QSVector path)
protected boolean	findCandidateOrphans(TreeKey treeKey, int level, QSVector leaderPath)
protected void	findOrphans(TreeKey treeKey, QSVector path, int level) A wrapper for findCandidateOrphans.
protected Set	getChildren(SecureHash treeId)
protected Set	getParents(SecureHash treeId)
Set	getRevpointers(Map revs, int level) Copied from Router.
protected void	handleAdoptionAck(QTreeGroupMsgAck ack)
protected void	handleAlarm() Only to be used in conjunction with resender.
protected void	handleClose(QTreeCloseMsg msg)
protected void	handleCloseAck(QTreeCloseMsgAck ack)
protected void	handleDeadParent(QTree.DeadParent event)
protected void	handleDown(QTreeDown down)
protected void	handleDownMsg(QTreeDownMsg msg)
protected void	handleDownMsgAck(QTreeDownMsgAck msg)
void	handleEvent(QueueElementIF item)
protected void	handleRepair(QTreeRepairMsg msg) Sent from the neglected child to the grandparent, then to the grand-grandparent, and so forth.
protected void	handleRevPtrsChanged(KbrReverseRoutingTableChanged changes)
protected void	handleRoutingTableChanged(KbrRoutingTableChanged changes)
protected void	handleUp(QTreeUp up) QTREE.API MESSAGE ROUTING
protected void	handleUpMsg(QTreeUpMsg msg)
protected void	handleUpMsgAck(QTreeUpMsgAck msg)
void	init(ConfigDataIF config)
protected void	markClosure(TreeKey key) Assumption made that key passed in has state CLOSED
protected boolean	markStability(TreeKey treeKey) Assume path, parent, everything but children are established for a given treeKey.
protected void	processCache() processCache clears out expired network messages from the cache.
int	profileSize()
protected void	recreateTree(TreeKey key, GuidAddr parent, boolean delay, QSVector path)
protected void	selfRoot(TreeKey treeKey)
protected void	updatePath(TreeKey treeKey, QSVector path)

Methods inherited from class ostore.util.StandardStage

BUG, BUG, BUG, destroy, dispatch, enqueue, handleEvents, now_ms, now_us

Methods inherited from class java.lang.Object

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

Field Detail

TIMEOUT_ADOPT

protected long TIMEOUT_ADOPT

TIMEOUT_DELAY

protected long TIMEOUT_DELAY

TIMEOUT_ACK

protected long TIMEOUT_ACK

TIMEOUT_MSG

protected long TIMEOUT_MSG

NUM_RETRIES

protected int NUM_RETRIES

OPENING

public static int OPENING

STABLE

public static int STABLE

CLOSED

public static int CLOSED

Constructor Detail

QTree

public QTree()

Method Detail

handleEvent

public void handleEvent(QueueElementIF item)
                 throws EventHandlerException

Specified by:

handleEvent in interface EventHandlerIF

EventHandlerException

processCache

protected void processCache()

processCache clears out expired network messages from the cache.

alterState

protected void alterState(QTreeStateMsg msg)

Only root receives a QTreeStateMsg. All other nodes will receive a join request to an existing parent of the tree. Calls selfRoot to look for possible nodes to adopt as children.

selfRoot

protected void selfRoot(TreeKey treeKey)

markStability

protected boolean markStability(TreeKey treeKey)

Assume path, parent, everything but children are established for a given treeKey. Remove the oldest existing treeKey from every data structure. if closing, do not add the tree_key and it should remove the oldest or all need to remove from tree_keys too - after running stability?

markClosure

protected void markClosure(TreeKey key)

Assumption made that key passed in has state CLOSED

updatePath

protected void updatePath(TreeKey treeKey,
                          QSVector path)

findOrphans

protected void findOrphans(TreeKey treeKey,
                           QSVector path,
                           int level)

A wrapper for findCandidateOrphans. Puts into a resender its request for children at a given level. If that fails, the handleAlarm() should realize if nodes fail to respond or NACK the request. If they NACK, then the resender should call findOrphans again, this time with a lower level request.

findCandidateOrphans

protected boolean findCandidateOrphans(TreeKey treeKey,
                                       int level,
                                       QSVector leaderPath)

contactCandidateOrphan

protected boolean contactCandidateOrphan(GuidAddr node,
                                         TreeKey treeKey,
                                         int level,
                                         QSVector path)

considerAdoption

protected void considerAdoption(QTreeGroupMsg msg)

chooseParent

protected void chooseParent(QTree.EvalPotParents event)

handleAdoptionAck

protected void handleAdoptionAck(QTreeGroupMsgAck ack)

closeChild

protected void closeChild(TreeKey key,
                          NodeId node)

closeParent

protected void closeParent(TreeKey key,
                           NodeId node)

handleRoutingTableChanged

protected void handleRoutingTableChanged(KbrRoutingTableChanged changes)

handleRevPtrsChanged

protected void handleRevPtrsChanged(KbrReverseRoutingTableChanged changes)

handleRepair

protected void handleRepair(QTreeRepairMsg msg)

Sent from the neglected child to the grandparent, then to the grand-grandparent, and so forth. Each higher generation, allow for Difference in Generation * DELAY time before dispatching a DeadParent later.

recreateTree

protected void recreateTree(TreeKey key,
                            GuidAddr parent,
                            boolean delay,
                            QSVector path)

handleDeadParent

protected void handleDeadParent(QTree.DeadParent event)

handleClose

protected void handleClose(QTreeCloseMsg msg)

handleCloseAck

protected void handleCloseAck(QTreeCloseMsgAck ack)

handleAlarm

protected void handleAlarm()

Only to be used in conjunction with resender. All other alarms should be handled by Classifer's dispatch_later.

handleUp

protected void handleUp(QTreeUp up)

QTREE.API MESSAGE ROUTING

handleUpMsg

protected void handleUpMsg(QTreeUpMsg msg)

handleUpMsgAck

protected void handleUpMsgAck(QTreeUpMsgAck msg)

handleDown

protected void handleDown(QTreeDown down)

handleDownMsg

protected void handleDownMsg(QTreeDownMsg msg)

handleDownMsgAck

protected void handleDownMsgAck(QTreeDownMsgAck msg)

init

public void init(ConfigDataIF config)
          throws Exception

Specified by:

init in interface EventHandlerIF

Overrides:

init in class StandardStage

Exception

profileSize

public int profileSize()

Specified by:

profileSize in interface ProfilableIF

getParents

protected Set getParents(SecureHash treeId)

getChildren

protected Set getChildren(SecureHash treeId)

getRevpointers

public Set getRevpointers(Map revs,
                          int level)

Copied from Router. Not implemented in Tapas.