Package org.apache.hadoop.ozone.container.checksum

Class ContainerMerkleTreeWriter

java.lang.Object
org.apache.hadoop.ozone.container.checksum.ContainerMerkleTreeWriter
public class ContainerMerkleTreeWriter extends Object
This class constructs a Merkle tree that provides one checksum for all data within a container. As the leaves of the tree, a checksum for each chunk is computed by taking a checksum of all checksums within that chunk. Each chunk checksum in a block is further checksummed together to generate the block level checksum. Finally, The checksums of all blocks are checksummed together to create a container level checksum. Note that checksums are order dependent. Chunk checksums are sorted by their offset within a block, and block checksums are sorted by their block ID. This class can be used to construct a consistent and completely filled ContainerProtos.ContainerMerkleTree object. It allows building a container merkle tree from scratch by incrementally adding chunks. The final checksums above the leaf levels of the tree are not calculated until toProto() is called.

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    static final Supplier<org.apache.hadoop.ozone.common.ChecksumByteBuffer>
    CHECKSUM_BUFFER_SUPPLIER
     

  • Constructor Summary

    Constructors
    Constructor
    Description
    ContainerMerkleTreeWriter()
    Constructs a writer for an initially empty container merkle tree.
    ContainerMerkleTreeWriter(org.apache.hadoop.hdds.protocol.datanode.proto.ContainerProtos.ContainerMerkleTree fromTree)
    Constructs a writer for a container merkle tree which initially contains all the information from the specified proto.

  • Method Summary

    Modifier and Type
    Method
    Description
    void
    addBlock(long blockID)
    Adds an empty block to the tree.
    void
    addChunks(long blockID, boolean checksumMatches, Collection<org.apache.hadoop.hdds.protocol.datanode.proto.ContainerProtos.ChunkInfo> chunks)
    Adds chunks to a block in the tree.
    void
    addChunks(long blockID, boolean checksumMatches, org.apache.hadoop.hdds.protocol.datanode.proto.ContainerProtos.ChunkInfo... chunks)
     
    org.apache.hadoop.hdds.protocol.datanode.proto.ContainerProtos.ContainerMerkleTree
    addDeletedBlocks(Collection<org.apache.hadoop.ozone.container.common.helpers.BlockData> blocks, boolean computeChecksum)
    Adds deleted blocks to this merkle tree.
    void
    setDeletedBlock(long blockID, long dataChecksum)
    Creates a deleted block entry in the merkle tree and assigns the block this fixed checksum.
    org.apache.hadoop.hdds.protocol.datanode.proto.ContainerProtos.ContainerMerkleTree
    toProto()
     
    org.apache.hadoop.hdds.protocol.datanode.proto.ContainerProtos.ContainerMerkleTree
    update(org.apache.hadoop.hdds.protocol.datanode.proto.ContainerProtos.ContainerMerkleTree existingTree)
    Merges the content from the provided tree with this tree writer.

    Methods inherited from class java.lang.Object

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

  • Field Details

    • CHECKSUM_BUFFER_SUPPLIER

      public static final Supplier<org.apache.hadoop.ozone.common.ChecksumByteBuffer> CHECKSUM_BUFFER_SUPPLIER

  • Constructor Details

    • ContainerMerkleTreeWriter

      public ContainerMerkleTreeWriter()
      Constructs a writer for an initially empty container merkle tree.

    • ContainerMerkleTreeWriter

      public ContainerMerkleTreeWriter(org.apache.hadoop.hdds.protocol.datanode.proto.ContainerProtos.ContainerMerkleTree fromTree)
      Constructs a writer for a container merkle tree which initially contains all the information from the specified proto.

  • Method Details

    • addChunks

      public void addChunks(long blockID, boolean checksumMatches, Collection<org.apache.hadoop.hdds.protocol.datanode.proto.ContainerProtos.ChunkInfo> chunks)
      Adds chunks to a block in the tree. The block entry will be created if it is the first time adding chunks to it. If the block entry already exists, the chunks will be added to the existing chunks for that block.
      Parameters:
      blockID - The ID of the block that these chunks belong to.
      checksumMatches - True if there were no checksum errors detected with these chunks. False indicates that all the chunks being added had checksum errors.
      chunks - A list of chunks to add to this block. The chunks will be sorted internally by their offset.

    • addChunks

      public void addChunks(long blockID, boolean checksumMatches, org.apache.hadoop.hdds.protocol.datanode.proto.ContainerProtos.ChunkInfo... chunks)

    • addBlock

      public void addBlock(long blockID)
      Adds an empty block to the tree. This method is not a pre-requisite to addChunks. If the block entry already exists, it will not be modified.
      Parameters:
      blockID - The ID of the empty block to add to the tree

    • setDeletedBlock

      public void setDeletedBlock(long blockID, long dataChecksum)
      Creates a deleted block entry in the merkle tree and assigns the block this fixed checksum. If the block already exists with child data it is overwritten. This method is used on the reconciliation path to update the data checksum used for a deleted block based on a peer's value.

    • update

      public org.apache.hadoop.hdds.protocol.datanode.proto.ContainerProtos.ContainerMerkleTree update(org.apache.hadoop.hdds.protocol.datanode.proto.ContainerProtos.ContainerMerkleTree existingTree)
      Merges the content from the provided tree with this tree writer. Conflicts where this tree writer and the incoming existingTree parameter have an entry for the same block are resolved in the following manner: - A deleted block supersedes a live block - Data cannot be un-deleted, so if a delete is ever witnessed, that is the state the block should converge to. - If both blocks are either deleted or live, the value in this writer supersedes the value in the existingTree parameter. - Our writer has the last witnessed information that is going to be persisted after this merge. For example, consider the case where a peer has deleted a block and we have a corrupt copy that has not yet been deleted. When we reconcile with this peer, we will mark the block as deleted and use the peer's checksum in our merkle tree to make the trees converge. The "fix" for corrupted data that is supposed to be deleted is to delete it. After this, if the scanner runs again before the block is deleted, we don't want to update the tree with the scanner's value because it would again diverge from the peer due to data that is expected to be deleted. This would cause the checksum to oscillate back and forth until the block is deleted, instead of converging.

    • addDeletedBlocks

      public org.apache.hadoop.hdds.protocol.datanode.proto.ContainerProtos.ContainerMerkleTree addDeletedBlocks(Collection<org.apache.hadoop.ozone.container.common.helpers.BlockData> blocks, boolean computeChecksum)
      Adds deleted blocks to this merkle tree. The blocks' checksums are computed from the checksums in the BlockData. If a block with the same ID already exists in the tree, it is overwritten as deleted with the checksum computed from the chunk checksums in the BlockData. If we reconciled with a peer and already marked this block as deleted during that process, this will overwrite that value. If it changes the block's checksum from what the peer had, one more round of reconciliation may be required to bring them in sync. The top level container data checksum is only computed in the returned tree proto if computeChecksum is true. If it is false, the resulting tree proto will have data checksums for each block, but an empty/unset data checksum for the container at the root of the tree.

    • toProto

      public org.apache.hadoop.hdds.protocol.datanode.proto.ContainerProtos.ContainerMerkleTree toProto()