rice.rm
Class RMImpl

java.lang.Object
  |
  +--rice.pastry.client.PastryAppl
        |
        +--rice.pastry.client.CommonAPIAppl
              |
              +--rice.rm.RMImpl

All Implemented Interfaces:

MessageReceiver, RM

public class RMImpl

extends CommonAPIAppl

implements RM

Version:

$Id: RMImpl.java,v 1.25 2003/07/23 21:20:19 animesh Exp $

Author:

Animesh Nandi

Nested Class Summary

static class

RMImpl.KEPenEntry This is the per entry state corresponding to the m_pendingRanges hashtable that we maintain in the Keys Exchange Protocol.

Field Summary

rice.pastry.routing.SendOptions	_sendOptions The SendOptions object to be used for all messaging through Pastry.
rice.rm.RMClient	app Application that uses this Replica Manager.
int	m_eId This is to keep track of events with respect to RMRequestKeysMsg only.
java.util.Hashtable	m_pendingEvents This table will be used by the Timeout mechanism in RMRequestKeysMsg.
java.util.Hashtable	m_pendingRanges This hashtable is keyed by the NodeId of the node to whom this local node is requesting for a set of keys in the Keys Exchange protocol.
int	m_seqno This will be incremented for every message that this node sends remotely.
static int	MAXKEYSINRANGE This value represents the maximum size of the keySet corresponding to a requested id range that we would like to fit in a single message.
rice.pastry.IdRange	myRange This represents the range of object identifiers in the Id space for which this node (by virtue of its position in the Id Space relative to the positions of the other Pastry nodes) is an i-root (0<=i<=k).
int	rFactor rFactor stands for the number of additional replicas for an object.
static int	SPLITFACTOR This value represents the splitting factor by which a range is split into in the Keys Exchange Protocol.

Fields inherited from class rice.pastry.client.PastryAppl

address, instance, thePastryNode

Constructor Summary

RMImpl(rice.pastry.PastryNode pn, rice.rm.RMClient _app, int _rFactor, java.lang.String instance)
Builds a new ReplicaManager(RM) associated with a particular RMclient.

Method Summary

void	addPendingEvent(rice.pastry.NodeId toNode, int eId) Used to insert entries to the m_pendingEvents hashtable
void	addPendingRange(rice.pastry.NodeId toNode, rice.pastry.IdRange reqRange) Used to insert a pending range to the m_pendingRanges hashtable
void	deliver(rice.pastry.Id key, rice.pastry.messaging.Message msg) Called by pastry when a message arrives for this application.
rice.pastry.security.Credentials	getCredentials() Returns the credentials for the application
rice.pastry.NodeHandle	getLocalHandle() Gets the local NodeHandle associated with this Pastry node.
rice.pastry.PastryNode	getPastryNode() Gets the underlying local Pastry node.
java.util.Vector	getPendingRanges(rice.pastry.NodeId toNode) Gets the list of pending Ranges corresponding to a node that we are communicating to in the Keys Exchange Protocol.
boolean	isPendingEvent(rice.pastry.NodeId toNode, int eId) Used to check for existence of an entry in the m_pendingEvents hashtable
boolean	isReady() Returns true if the RM substrate is ready.
void	lookupForward(rice.pastry.routing.RouteMessage msg) Called by client(RMClient) to enable optimizations to route to the nearest replica.
void	notifyReady() This is called when the underlying pastry node is ready.
void	periodicMaintenance() This is the periodic maintenance protocol which removes stale objects as well as checks to see if there is any missing object.
void	printPendingRanges(rice.pastry.NodeId toNode) Prints the list of pending Ranges corresponding to a node that we are communicating to in the Keys Exchange Protocol.
void	registerKey(rice.pastry.Id key) Called by client(RMClient) to notify the RM substrate of the presence of a key corresponding to a object that was 'recently' inserted at itself.
void	removePendingEvent(rice.pastry.NodeId toNode, int eId) Used to remove entries to the m_pendingEvents hashtable
void	removePendingRange(rice.pastry.NodeId toNode, rice.pastry.IdRange reqRange) Used to remove a pending range to the m_pendingRanges hashtable
void	sendKeyRequestMessages(rice.pastry.NodeSet set, java.util.Vector rangeSet) We send RMRequestKeys messages to the the nodes in the 'set' asking for keys in the ranges specified in the 'rangeSet'.
void	splitPendingRanges(rice.pastry.NodeId toNode) Iterates over the list of pending Ranges and splits the ranges if the expected number of keys in a range is greater than MAXKEYSINRANGE.
void	update(rice.pastry.NodeHandle nh, boolean wasAdded) Implements the main algorithm for keeping the invariant that an object would be stored in k closest nodes to the objectKey while the nodes are coming up or going down.
void	updatePendingRange(rice.pastry.NodeId toNode, rice.pastry.IdRange reqRange, int numKeys) Used to update the state of a pending range to the m_pendingRanges hashtable.

Methods inherited from class rice.pastry.client.CommonAPIAppl

forward, leafSetChange, localLookup, messageForAppl, neighborSet, range, range, receiveMessage, replicaSet, route

Methods inherited from class rice.pastry.client.PastryAppl

enrouteMessage, getAddress, getLeafSet, getNodeHandle, getNodeId, getRoutingTable, isClosest, registerReceiver, routeMsg, routeMsgDirect, routeSetChange, sendMessage

Methods inherited from class java.lang.Object

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

Field Detail

_sendOptions

public rice.pastry.routing.SendOptions _sendOptions

The SendOptions object to be used for all messaging through Pastry.

m_seqno

public int m_seqno

This will be incremented for every message that this node sends remotely. Specifically, incremented for every RMRequestKeysMsg, RMResponseKeysMsg it sends. This is to aid in the debugging phase.

m_eId

public int m_eId

This is to keep track of events with respect to RMRequestKeysMsg only. Since RMRequestKeysMsg is the only message that needs a timeout mechanism. Incremented for every different RMRequestKeys message generation event. That is if a Timeout occurred for a RMRequestKeysMsg, then the subsequent RMRequestKeysMsg, that will be resent will have the SAME eventId but an increased value of seqNo.

myRange

public rice.pastry.IdRange myRange

This represents the range of object identifiers in the Id space for which this node (by virtue of its position in the Id Space relative to the positions of the other Pastry nodes) is an i-root (0<=i<=k).

rFactor

public int rFactor

rFactor stands for the number of additional replicas for an object. The primary replica is denoted a 0-root, other replicas are denoted as i-root (1<=i<=rFactor).

app

public rice.rm.RMClient app

Application that uses this Replica Manager.

m_pendingRanges

public java.util.Hashtable m_pendingRanges

This hashtable is keyed by the NodeId of the node to whom this local node is requesting for a set of keys in the Keys Exchange protocol. Since potentially the number of keys in a particular range could be very high, asking for the entire set of keys in the intial range could result in huge packet sizes. In order to circumvent this problem, we devise some strategies in the Keys Exchange protocol to split this range into smaller ranges and issue requests for these subranges one at a time. This requires state in the form of this hashtable to maintain the list f pending ranges, for which a request for the key set is yet to be issued.

m_pendingEvents

public java.util.Hashtable m_pendingEvents

This table will be used by the Timeout mechanism in RMRequestKeysMsg.

MAXKEYSINRANGE

public static int MAXKEYSINRANGE

This value represents the maximum size of the keySet corresponding to a requested id range that we would like to fit in a single message. As a result of this, we need some strategies to split ranges in the Keys Exchange Protocol.

SPLITFACTOR

public static int SPLITFACTOR

This value represents the splitting factor by which a range is split into in the Keys Exchange Protocol. The splitting method is recursive binary splitting until we split the range into a total of SPLITFACTOR parts.

Constructor Detail

RMImpl

public RMImpl(rice.pastry.PastryNode pn,
              rice.rm.RMClient _app,
              int _rFactor,
              java.lang.String instance)

Builds a new ReplicaManager(RM) associated with a particular RMclient.

Parameters:

pn - the PastryNode associated with this application

_app - the client associated with this replica manager

_rFactor - the replicaFactor associated with the replica manager

instance - the string used to sucessfully instantiate different application instances on the same pastry node

Method Detail

isReady

public boolean isReady()

Returns true if the RM substrate is ready. The RM substrate is ready when underlying PastryNode is ready.

getLocalHandle

public rice.pastry.NodeHandle getLocalHandle()

Gets the local NodeHandle associated with this Pastry node.

Returns:

local handle of the underlying pastry node.

getPastryNode

public rice.pastry.PastryNode getPastryNode()

Gets the underlying local Pastry node.

Returns:

local pastry node.

addPendingEvent

public void addPendingEvent(rice.pastry.NodeId toNode,
                            int eId)

Used to insert entries to the m_pendingEvents hashtable

Parameters:

toNode - the node with whom the local node is communicating this is the key for this entry in the hashtable

eId - the event Id associated with this RMRequestKeys msg.

removePendingEvent

public void removePendingEvent(rice.pastry.NodeId toNode,
                               int eId)

Used to remove entries to the m_pendingEvents hashtable

Parameters:

toNode - the node with whom the local node is communicating this is the key for this entry in the hashtable

eId - the event Id associated with this RMRequestKeys msg.

isPendingEvent

public boolean isPendingEvent(rice.pastry.NodeId toNode,
                              int eId)

Used to check for existence of an entry in the m_pendingEvents hashtable

Parameters:

toNode - the node with whom the local node is communicating this is the key for this entry in the hashtable

eId - the event Id associated with this RMRequestKeys msg.

addPendingRange

public void addPendingRange(rice.pastry.NodeId toNode,
                            rice.pastry.IdRange reqRange)

Used to insert a pending range to the m_pendingRanges hashtable

Parameters:

toNode - the node with whom the local node is communicating this is the key for this entry in the hashtable

reqRange - the pending range.

updatePendingRange

public void updatePendingRange(rice.pastry.NodeId toNode,
                               rice.pastry.IdRange reqRange,
                               int numKeys)

Used to update the state of a pending range to the m_pendingRanges hashtable.

Parameters:

toNode - the node with whom the local node is communicating this is the key for this entry in the hashtable

reqRange - the pending range.

numKeys - the expected number of keys associated with this subrange

removePendingRange

public void removePendingRange(rice.pastry.NodeId toNode,
                               rice.pastry.IdRange reqRange)

Used to remove a pending range to the m_pendingRanges hashtable

Parameters:

toNode - the node with whom the local node is communicating this is the key for this entry in the hashtable

reqRange - the pending range.

splitPendingRanges

public void splitPendingRanges(rice.pastry.NodeId toNode)

Iterates over the list of pending Ranges and splits the ranges if the expected number of keys in a range is greater than MAXKEYSINRANGE.

Parameters:

toNode - the node with which this local was communicating in the keys exchange protocol.

getPendingRanges

public java.util.Vector getPendingRanges(rice.pastry.NodeId toNode)

Gets the list of pending Ranges corresponding to a node that we are communicating to in the Keys Exchange Protocol.

Parameters:

toNode - the node with which this local was communicating in the keys exchange protocol.

printPendingRanges

public void printPendingRanges(rice.pastry.NodeId toNode)

Prints the list of pending Ranges corresponding to a node that we are communicating to in the Keys Exchange Protocol.

Parameters:

toNode - the node with which this local was communicating in the keys exchange protocol.

deliver

public void deliver(rice.pastry.Id key,
                    rice.pastry.messaging.Message msg)

Called by pastry when a message arrives for this application.

Specified by:

deliver in class CommonAPIAppl

Parameters:

msg - the message that is arriving.

notifyReady

public void notifyReady()

This is called when the underlying pastry node is ready.

Overrides:

notifyReady in class CommonAPIAppl

periodicMaintenance

public void periodicMaintenance()

This is the periodic maintenance protocol which removes stale objects as well as checks to see if there is any missing object. This call is invoked by the RMMaintenanceMsg message that is scheduled to be periodically invoked at the local node.

getCredentials

public rice.pastry.security.Credentials getCredentials()

Returns the credentials for the application

Specified by:

getCredentials in class CommonAPIAppl

Returns:

the credentials

update

public void update(rice.pastry.NodeHandle nh,
                   boolean wasAdded)

Implements the main algorithm for keeping the invariant that an object would be stored in k closest nodes to the objectKey while the nodes are coming up or going down.

Overrides:

update in class CommonAPIAppl

Parameters:

nh - NodeHandle of the node which caused the neighborSet change

wasAdded - true if added, false if removed

sendKeyRequestMessages

public void sendKeyRequestMessages(rice.pastry.NodeSet set,
                                   java.util.Vector rangeSet)

We send RMRequestKeys messages to the the nodes in the 'set' asking for keys in the ranges specified in the 'rangeSet'. Additionally, in order to implement the TIMEOUT mechanism to handle loss of RMRequestKeysMsg, we wrap the RMRequestKeysMsg in a RMTimeoutMsg which we schedule on the local node after a TIMEOUT period.

registerKey

public void registerKey(rice.pastry.Id key)

Called by client(RMClient) to notify the RM substrate of the presence of a key corresponding to a object that was 'recently' inserted at itself. The RM substrate algorithm is designed on a Pull model. This call however gives the RM substrate to implement the Push model if it desires so in future. The current implementation this method is non-operational since we believe that the Pull model behaves sufficiently well.

Specified by:

registerKey in interface RM

Parameters:

key - the object identifier

lookupForward

public void lookupForward(rice.pastry.routing.RouteMessage msg)

Called by client(RMClient) to enable optimizations to route to the nearest replica. Should be called by client in the context of the forward method of a lookup message. Should only be called if the local client does not have the desired object. This call could change the nextHop field in the RouteMessage.

Specified by:

lookupForward in interface RM

Parameters:

msg - the RouteMessage