public interface MerkleTree
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.
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
|
void updateAdd(Object key, Object value)
key
- The key that value belongs tovalue
- The value of the added entryvoid updateReplace(Object key, Object oldValue, Object newValue)
key
- The key that values belong tooldValue
- The old value of the replaced entrynewValue
- The new value of the replaced entryvoid updateRemove(Object key, Object removedValue)
key
- The key that values belong toremovedValue
- The value of the entry removed from the
underlying data structurevoid forEachKeyOfNode(int nodeOrder, Consumer<Object> consumer)
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.
nodeOrder
- The node for which all keysconsumer
- The action which is called for each keyint getNodeKeyCount(int nodeOrder)
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
nodeOrder
- The node for which the key count is queriedlong footprint()
void clear()
int getNodeHash(int nodeOrder)
nodeOrder
nodeOrder
- The order of the nodeint depth()
Copyright © 2018 Hazelcast, Inc.. All Rights Reserved.