Package com.usatiuk.kleppmanntree

Class KleppmannTree<TimestampT extends Comparable<TimestampT>,PeerIdT extends Comparable<PeerIdT>,MetaT extends NodeMeta,NodeIdT>

java.lang.Object

com.usatiuk.kleppmanntree.KleppmannTree<TimestampT,PeerIdT,MetaT,NodeIdT>

Type Parameters:

TimestampT - Type of the timestamp

PeerIdT - Type of the peer ID

MetaT - Type of the node metadata

NodeIdT - Type of the node ID

public class KleppmannTree<TimestampT extends Comparable<TimestampT>,PeerIdT extends Comparable<PeerIdT>,MetaT extends NodeMeta,NodeIdT>
extends Object

An implementation of a tree as described in A highly-available move operation for replicated trees

Constructor Summary

Constructors

Constructor	Description
KleppmannTree(StorageInterface<TimestampT,PeerIdT,MetaT,NodeIdT> storage, PeerInterface<PeerIdT> peers, Clock<TimestampT> clock, OpRecorder<TimestampT,PeerIdT,MetaT,NodeIdT> opRecorder)	Constructor with all the dependencies

Method Summary

Modifier and Type	Method	Description
void	applyExternalOp(PeerIdT from, OpMove<TimestampT,PeerIdT,MetaT,NodeIdT> op)	Apply an external operation from a remote peer
org.apache.commons.lang3.tuple.Pair<String,NodeIdT>	findParent(Function<TreeNode<TimestampT,PeerIdT,MetaT,NodeIdT>,Boolean> kidPredicate)	Find the parent of a node that matches the given predicate
<LocalMetaT extends MetaT> void	move(NodeIdT newParent, LocalMetaT newMeta, NodeIdT child)	Move a node to a new parent with new metadata
void	move(NodeIdT newParent, MetaT newMeta, NodeIdT child, boolean failCreatingIfExists)	Move a node to a new parent with new metadata
void	recordBoostrapFor(PeerIdT host)	Record the bootstrap operations for a given peer Will visit all nodes of the tree and add their effective operations to both the queue to be sent to the peer, and to the global operation log.
NodeIdT	traverse(List<String> names)	Traverse the tree from its root node using the given list of names
void	updateExternalTimestamp(PeerIdT from, TimestampT timestamp)	Update the causality threshold timestamp for a peer
void	walkTree(Consumer<TreeNode<TimestampT,PeerIdT,MetaT,NodeIdT>> consumer)	Walk the tree and apply the given consumer to each node

Methods inherited from class java.lang.Object

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

Constructor Details

KleppmannTree

public KleppmannTree(StorageInterface<TimestampT,PeerIdT,MetaT,NodeIdT> storage,
 PeerInterface<PeerIdT> peers,
 Clock<TimestampT> clock,
 OpRecorder<TimestampT,PeerIdT,MetaT,NodeIdT> opRecorder)

Constructor with all the dependencies

Parameters:

storage - Storage interface

peers - Peer interface

clock - Clock interface

opRecorder - Operation recorder interface

Method Details

traverse

public NodeIdT traverse(List<String> names)

Traverse the tree from its root node using the given list of names

Parameters:

names - The list of names to traverse

Returns:

The resulting node ID or null if not found

move

public <LocalMetaT extends MetaT> void move(NodeIdT newParent,
 LocalMetaT newMeta,
 NodeIdT child)

Move a node to a new parent with new metadata

Parameters:

newParent - The new parent node ID

newMeta - The new metadata

child - The child node ID

Throws:

AlreadyExistsException - If the node already exists and failCreatingIfExists is true

move

public void move(NodeIdT newParent,
 MetaT newMeta,
 NodeIdT child,
 boolean failCreatingIfExists)

Move a node to a new parent with new metadata

Parameters:

newParent - The new parent node ID

newMeta - The new metadata

child - The child node ID

failCreatingIfExists - Whether to fail if there is a name conflict, otherwise replace the existing node

Throws:

AlreadyExistsException - If the node already exists and failCreatingIfExists is true

applyExternalOp

public void applyExternalOp(PeerIdT from,
 OpMove<TimestampT,PeerIdT,MetaT,NodeIdT> op)

Apply an external operation from a remote peer

Parameters:

from - The peer ID

op - The operation to apply

updateExternalTimestamp

public void updateExternalTimestamp(PeerIdT from,
 TimestampT timestamp)

Update the causality threshold timestamp for a peer

Parameters:

from - The peer ID

timestamp - The timestamp received from it

walkTree

public void walkTree(Consumer<TreeNode<TimestampT,PeerIdT,MetaT,NodeIdT>> consumer)

Walk the tree and apply the given consumer to each node

Parameters:

consumer - The consumer to apply to each node

findParent

public org.apache.commons.lang3.tuple.Pair<String,NodeIdT> findParent(Function<TreeNode<TimestampT,PeerIdT,MetaT,NodeIdT>,Boolean> kidPredicate)

Find the parent of a node that matches the given predicate

Parameters:

kidPredicate - The predicate to match the child node

Returns:

A pair containing the name of the child and the ID of the parent, or null if not found

recordBoostrapFor

public void recordBoostrapFor(PeerIdT host)

Record the bootstrap operations for a given peer Will visit all nodes of the tree and add their effective operations to both the queue to be sent to the peer, and to the global operation log.

Parameters:

host - The peer ID