com.hazelcast.wan.merkletree

Interface MerkleTree

All Known Implementing Classes:

ArrayMerkleTree

public interface MerkleTree

Interface defining methods for Merkle tree implementations

A Merkle tree is a perfect binary tree in which every leaf node holds the hash of a data block and every non-leaf node holds the hash of its children nodes.

In WAN replication Merkle trees are used for building a difference based anti-entropy mechanism in which the source and the target clusters identify the data blocks that need to be transferred from the source to the target, aiming to reduce the network traffic and the time required for getting the clusters in sync.

Since the Merkle trees may be updated concurrently on the clusters the order of the updates (addition, removal and amendment of the entries in the underlying data structure) may be different. This limits the applicable hash functions to the ones that are associative. This limitation ensures that the same set of entries added in any arbitrary order will result the same hash. Using a non-associative hash function may lead to different hashes calculated in the different clusters if the entries are added in different order, which comes with unnecessary data synchronization.

Method Summary

Modifier and Type	Method and Description
void	clear() Clears the Merkle tree
int	depth() Returns the depth of the tree
long	footprint() Returns the memory footprint of Merkle Tree in bytes
void	forEachKeyOfNode(int nodeOrder, Consumer<Object> consumer) Performs the given action for each key of the specified node until all elements have been processed or the action throws an exception.
int	getNodeHash(int nodeOrder) Returns the hash for the node with the given nodeOrder
int	getNodeKeyCount(int nodeOrder) Returns the number of the keys under the specified node.
void	updateAdd(Object key, Object value) Updating the tree with adding a new entry to the tree
void	updateRemove(Object key, Object removedValue) Updating the tree with removing an entry
void	updateReplace(Object key, Object oldValue, Object newValue) Updating the tree with replacing an old value with a new one

Method Detail

updateAdd

void updateAdd(Object key,
               Object value)

Updating the tree with adding a new entry to the tree

Parameters:

key - The key that value belongs to

value - The value of the added entry

updateReplace

void updateReplace(Object key,
                   Object oldValue,
                   Object newValue)

Updating the tree with replacing an old value with a new one

Parameters:

key - The key that values belong to

oldValue - The old value of the replaced entry

newValue - The new value of the replaced entry

updateRemove

void updateRemove(Object key,
                  Object removedValue)

Updating the tree with removing an entry

Parameters:

key - The key that values belong to

removedValue - The value of the entry removed from the underlying data structure

forEachKeyOfNode

void forEachKeyOfNode(int nodeOrder,
                      Consumer<Object> consumer)

Performs the given action for each key of the specified node until all elements have been processed or the action throws an exception.

The node referenced by nodeOrder can be either a leaf or a non-leaf node. In the latter case consumer is called for each key that belong the the leaves of the subtree under the specified node.

This method does not define ordering for the keys belong to the node nodeOrder, therefore the caller should not rely on it.

Parameters:

nodeOrder - The node for which all keys

consumer - The action which is called for each key

getNodeKeyCount

int getNodeKeyCount(int nodeOrder)

Returns the number of the keys under the specified node.

The node referenced by nodeOrder can be either a leaf or a non-leaf node. In the latter case the method returns with the sum of the key counts of the subtree under the specified node

Parameters:

nodeOrder - The node for which the key count is queried

Returns:

the number of the keys under the specified node

footprint

long footprint()

Returns the memory footprint of Merkle Tree in bytes

Returns:

the memory footprint of the Merkle Tree in bytes

clear

void clear()

Clears the Merkle tree

getNodeHash

int getNodeHash(int nodeOrder)

Returns the hash for the node with the given nodeOrder

Parameters:

nodeOrder - The order of the node

Returns:

the hash of the node

depth

int depth()

Returns the depth of the tree

Returns:

the depth of the tree