MerkleTree (apache-cassandra API)
Date: 2014-10-21

org.apache.cassandra.utils

## Class MerkleTree

- java.lang.Object
- - org.apache.cassandra.utils.MerkleTree

- All Implemented Interfaces:
    java.io.Serializable

      public class MerkleTree
      extends java.lang.Object
      implements java.io.Serializable

  A MerkleTree implemented as a binary tree. A MerkleTree is a full binary tree that represents a perfect binary tree of depth 'hashdepth'. In a perfect binary tree, each leaf contains a sequentially hashed range, and each inner node contains the binary hash of its two children. In the MerkleTree, many ranges will not be split to the full depth of the perfect binary tree: the leaves of this tree are Leaf objects, which contain the computed values of the nodes that would be below them if the tree were perfect. The hash values of the inner nodes of the MerkleTree are calculated lazily based on their children when the hash of a range is requested with hash(range). Inputs passed to TreeRange.validate should be calculated using a very secure hash, because all hashing internal to the tree is accomplished using XOR. If two MerkleTrees have the same hashdepth, they represent a perfect tree of the same depth, and can always be compared, regardless of size or splits.
  See Also:
    Serialized Form

- - ### Nested Class Summary

    Nested Classes
    Modifier and Type | Class and Description
    --- | ---
    `static class` | `MerkleTree.MerkleTreeSerializer`
    `static class` | `MerkleTree.RowHash` Hash value representing a row, to be used to pass hashes to the MerkleTree.
    `static class` | `MerkleTree.TreeDifference`
    `static class` | `MerkleTree.TreeRange` The public interface to a range in the tree.
    `static class` | `MerkleTree.TreeRangeIterator` Returns the leaf (range) of a given tree in increasing order.

  - ### Field Summary

    Fields
    Modifier and Type | Field and Description
    --- | ---
    `static int` | `CONSISTENT`
    `Range<Token>` | `fullRange` The top level range that this MerkleTree covers.
    `static int` | `FULLY_INCONSISTENT`
    `byte` | `hashdepth`
    `static int` | `PARTIALLY_INCONSISTENT`
    `static byte` | `RECOMMENDED_DEPTH`
    `static MerkleTree.MerkleTreeSerializer` | `serializer`

  - ### Constructor Summary

    Constructors
    Constructor and Description
    `MerkleTree(IPartitioner partitioner, Range<Token> range, byte hashdepth, long maxsize)`

  - ### Method Summary

    Methods
    Modifier and Type | Method and Description
    --- | ---
    `static java.util.List<MerkleTree.TreeRange>` | `difference(MerkleTree ltree, MerkleTree rtree)`
    `MerkleTree.TreeRange` | `get(Token t)` For testing purposes.
    `byte[]` | `hash(Range<Token> range)` Hash the given range in the tree.
    `EstimatedHistogram` | `histogramOfRowCountPerLeaf()`
    `EstimatedHistogram` | `histogramOfRowSizePerLeaf()`
    `void` | `init()` Initializes this tree by splitting it until hashdepth is reached, or until an additional level of splits would violate maxsize.
    `void` | `invalidate(Token t)` Invalidates the ranges containing the given token.
    `MerkleTree.TreeRangeIterator` | `invalids()` Returns a lazy iterator of invalid TreeRanges that need to be filled in order to make the given Range valid.
    `long` | `maxsize()`
    `void` | `maxsize(long maxsize)`
    `IPartitioner` | `partitioner()`
    `long` | `size()` The number of distinct ranges contained in this tree.
    `boolean` | `split(Token t)` Splits the range containing the given token, if no tree limits would be violated.
    `java.lang.String` | `toString()`

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

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

- - ### Field Detail

    - #### serializer

          public static final MerkleTree.MerkleTreeSerializer serializer

    - #### RECOMMENDED_DEPTH

          public static final byte RECOMMENDED_DEPTH

      See Also:
        Constant Field Values

    - #### CONSISTENT

          public static final int CONSISTENT

      See Also:
        Constant Field Values

    - #### FULLY_INCONSISTENT

          public static final int FULLY_INCONSISTENT

      See Also:
        Constant Field Values

    - #### PARTIALLY_INCONSISTENT

          public static final int PARTIALLY_INCONSISTENT

      See Also:
        Constant Field Values

    - #### hashdepth

          public final byte hashdepth

    - #### fullRange

          public final Range<Token> fullRange

      The top level range that this MerkleTree covers.

  - ### Constructor Detail

    - #### MerkleTree

          public MerkleTree(IPartitioner partitioner,
                    Range<Token> range,
                    byte hashdepth,
                    long maxsize)

      Parameters:
        `partitioner` - The partitioner in use.
        `range` - the range this tree covers
        `hashdepth` - The maximum depth of the tree. 100/(2^depth) is the % of the key space covered by each subrange of a fully populated tree.
        `maxsize` - The maximum number of subranges in the tree.

  - ### Method Detail

    - #### init

          public void init()

      Initializes this tree by splitting it until hashdepth is reached, or until an additional level of splits would violate maxsize. NB: Replaces all nodes in the tree.

    - #### partitioner

          public IPartitioner partitioner()

    - #### size

          public long size()

      The number of distinct ranges contained in this tree. This is a reasonable measure of the memory usage of the tree (assuming 'this.order' is significant).

    - #### maxsize

          public long maxsize()

    - #### maxsize

          public void maxsize(long maxsize)

    - #### difference

          public static java.util.List<MerkleTree.TreeRange> difference(MerkleTree ltree,
                                                        MerkleTree rtree)

      Parameters:
        `ltree` - First tree.
        `rtree` - Second tree.
      Returns:
        A list of the largest contiguous ranges where the given trees disagree.

    - #### get

          public MerkleTree.TreeRange get(Token t)

      For testing purposes. Gets the smallest range containing the token.

    - #### invalidate

          public void invalidate(Token t)

      Invalidates the ranges containing the given token. Useful for testing.

    - #### hash

          public byte[] hash(Range<Token> range)

      Hash the given range in the tree. The range must have been generated with recursive applications of partitioner.midpoint(). NB: Currently does not support wrapping ranges that do not end with partitioner.getMinimumToken().
      Returns:
        Null if any subrange of the range is invalid, or if the exact range cannot be calculated using this tree.

    - #### split

          public boolean split(Token t)

      Splits the range containing the given token, if no tree limits would be violated. If the range would be split to a depth below hashdepth, or if the tree already contains maxsize subranges, this operation will fail.
      Returns:
        True if the range was successfully split.

    - #### invalids

          public MerkleTree.TreeRangeIterator invalids()

      Returns a lazy iterator of invalid TreeRanges that need to be filled in order to make the given Range valid.

    - #### histogramOfRowSizePerLeaf

          public EstimatedHistogram histogramOfRowSizePerLeaf()

    - #### histogramOfRowCountPerLeaf

          public EstimatedHistogram histogramOfRowCountPerLeaf()

    - #### toString

          public java.lang.String toString()

      Overrides:
        `toString` in class `java.lang.Object`

Copyright © 2014 The Apache Software Foundation