com.hazelcast.wan.merkletree

## Class ArrayMerkleTree

- java.lang.Object
- - com.hazelcast.wan.merkletree.ArrayMerkleTree

- All Implemented Interfaces:
    MerkleTree

      public class ArrayMerkleTree
      extends Object
      implements MerkleTree

  A not thread-safe, array based `MerkleTree` implementation, which represents each node of the tree as a single `int` containing the node's hash.

  The array representation of the tree comes with optimal memory footprint and memory layout. The memory layout is leveraged by the breadth-first (and breadth-last) traversal of the tree such as recalculating the hash for each non-leaf node. This traversal is optimal, since it is a sequential memory walk coming with low CPU cache miss rates, which in the case of a deep tree enables much better performance compared to the linked representation of the tree.

  The nodes in this implementation are referenced by their breadth-first order in the tree. Using this order as reference comes with the following properties:

  - The order of a node is unique for each node and refers to the node on the same level and position in every binary tree. This makes a single node easily referable even between clusters.
  - The order of a node intrinsically encodes the level of the tree on which the given node is. See `MerkleTreeUtil.getLevelOfNode(int)`
  - The order of a node also intrinsically encodes the hash range that the node covers since the followings are known based on the order:
    1. the level the node is on
    2. the number of the nodes on the same level
    3. the node's relative order from the leftmost node on the same level
    4. because of the points above and that the codomain of the hash function is known (32 bit ints), the range of the hashes that a single node on the given level covers is known, hence the range covered by a concrete node can be calculated. See `MerkleTreeUtil.getNodeHashRangeOnLevel(int)`, `MerkleTreeUtil.getNodeRangeLow(int)`, `MerkleTreeUtil.getNodeRangeHigh(int)`
  - The offset of a node can be calculated easily and cheaply with as `offset = order * NODE_SIZE`.

  Every leaf of the tree may cover multiple elements in the underlying data structure. These elements are key-value pairs and the keys of the elements are stored in a data structure that are referred to as data blocks. This implementation stores the keys in `OAHashSet`s, one set for each leaf. These sets are initialized in tree construction time eagerly with initial capacity one.

  This implementation updates the tree synchronously. It can do that, since updating a leaf's hash doesn't need to access the values belong to the leaf, thank to the not order-sensitive hash function in use. See `MerkleTreeUtil.addHash(int, int)`, `MerkleTreeUtil.removeHash(int, int)`, `MerkleTreeUtil.sumHash(int, int)`

- - ### Field Summary

    Fields
    Modifier and Type | Field and Description
    --- | ---
    `protected int` | `depth`
    `protected int` | `leafLevelOrder`
    `protected int[]` | `tree`

  - ### Constructor Summary

    Constructors
    Constructor and Description
    `ArrayMerkleTree(int depth)`

  - ### Method Summary

    All Methods Instance Methods Abstract Methods Concrete Methods
    Modifier and Type | Method and Description
    --- | ---
    `void` | `clear()` Clears the Merkle tree
    `int` | `depth()` Returns the depth of the 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.
    `protected void` | `setNodeHash(int nodeOrder, int hash)`
    `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

    - ### Methods inherited from class java.lang.Object

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

- - ### Field Detail

    - #### tree

          protected final int[] tree

    - #### depth

          protected final int depth

    - #### leafLevelOrder

          protected final int leafLevelOrder

  - ### Constructor Detail

    - #### ArrayMerkleTree

          public ArrayMerkleTree(int depth)

  - ### Method Detail

    - #### updateAdd

          public void updateAdd(Object key,
                                Object value)

      Description copied from interface: `MerkleTree`
      Updating the tree with adding a new entry to the tree
      Specified by:
        `updateAdd` in interface `MerkleTree`
      Parameters:
        `key` - The key that value belongs to
        `value` - The value of the added entry

    - #### updateReplace

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

      Description copied from interface: `MerkleTree`
      Updating the tree with replacing an old value with a new one
      Specified by:
        `updateReplace` in interface `MerkleTree`
      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

          public void updateRemove(Object key,
                                   Object removedValue)

      Description copied from interface: `MerkleTree`
      Updating the tree with removing an entry
      Specified by:
        `updateRemove` in interface `MerkleTree`
      Parameters:
        `key` - The key that values belong to
        `removedValue` - The value of the entry removed from the underlying data structure

    - #### getNodeHash

          public 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

    - #### forEachKeyOfNode

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

      Description copied from interface: `MerkleTree`
      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.

      Specified by:
        `forEachKeyOfNode` in interface `MerkleTree`
      Parameters:
        `nodeOrder` - The node for which all keys
        `consumer` - The action which is called for each key

    - #### getNodeKeyCount

          public int getNodeKeyCount(int nodeOrder)

      Description copied from interface: `MerkleTree`
      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

      Specified by:
        `getNodeKeyCount` in interface `MerkleTree`
      Parameters:
        `nodeOrder` - The node for which the key count is queried
      Returns:
        the number of the keys under the specified node

    - #### footprint

          public long footprint()

      Description copied from interface: `MerkleTree`
      Returns the memory footprint of Merkle Tree in bytes
      Specified by:
        `footprint` in interface `MerkleTree`
      Returns:
        the memory footprint of the Merkle Tree in bytes

    - #### clear

          public void clear()

      Description copied from interface: `MerkleTree`
      Clears the Merkle tree
      Specified by:
        `clear` in interface `MerkleTree`

    - #### depth

          public int depth()

      Returns the depth of the tree
      Returns:
        the depth of the tree

    - #### setNodeHash

          protected void setNodeHash(int nodeOrder,
                                     int hash)

    - #### depth

          public int depth()

      Returns the depth of the tree
      Returns:
        the depth of the tree

Copyright © 2019. All rights reserved.