aswinshakil commented on code in PR #9015:
URL: https://github.com/apache/ozone/pull/9015#discussion_r2338264877
##########
hadoop-hdds/container-service/src/main/java/org/apache/hadoop/ozone/container/checksum/ContainerMerkleTreeWriter.java:
##########
@@ -111,13 +110,82 @@ public void addBlock(long blockID) {
id2Block.computeIfAbsent(blockID, BlockMerkleTreeWriter::new);
}
+ /**
+ * 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.
+ */
+ public void setDeletedBlock(long blockID, long dataChecksum) {
+ BlockMerkleTreeWriter blockWriter = new BlockMerkleTreeWriter(blockID);
+ blockWriter.markDeleted(dataChecksum);
+ id2Block.put(blockID, blockWriter);
+ }
+
+ /**
+ * 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.
+ */
+ public ContainerProtos.ContainerMerkleTree
update(ContainerProtos.ContainerMerkleTree existingTree) {
+ for (ContainerProtos.BlockMerkleTree existingBlockTree:
existingTree.getBlockMerkleTreeList()) {
+ long blockID = existingBlockTree.getBlockID();
+ BlockMerkleTreeWriter ourBlockTree = id2Block.get(blockID);
+ if (ourBlockTree != null) {
+ // both trees contain the block. We will only consider the
incoming/existing value if it does not match our
+ // current state
+ if (!ourBlockTree.isDeleted() && existingBlockTree.getDeleted()) {
+ setDeletedBlock(blockID, existingBlockTree.getDataChecksum());
+ }
+ // In all other cases, keep using our writer's value over the existing
one because either:
+ // - The deleted states match between the two blocks OR
+ // - Our block is deleted and the existing one is not, so we have the
latest value to use.
+ } else if (existingBlockTree.getDeleted()) {
+ // Our tree does not have this block. Only take the value if it is
deleted.
+ // The definitive set of live blocks will come from this tree writer.
+ setDeletedBlock(blockID, existingBlockTree.getDataChecksum());
+ }
+ }
+ return toProtoBuilder().build();
+ }
+
+ public ContainerProtos.ContainerMerkleTree
addDeletedBlocks(Collection<BlockData> blocks, boolean computeChecksum) {
+ for (BlockData block: blocks) {
+ long blockID = block.getLocalID();
+ BlockMerkleTreeWriter blockWriter = new BlockMerkleTreeWriter(blockID);
+ for (ContainerProtos.ChunkInfo chunkInfo: block.getChunks()) {
+ blockWriter.addChunks(new ChunkMerkleTreeWriter(chunkInfo, true));
+ }
+ blockWriter.markDeleted();
+ id2Block.put(blockID, blockWriter);
+ }
+ ContainerProtos.ContainerMerkleTree.Builder protoBuilder =
toProtoBuilder();
+ if (!computeChecksum) {
Review Comment:
Can we have some more comments on when we would be actually computing the
checksum, like in the case after an upgrade when the `BlockDeletingService`
runs it needs to calculate the checksum. But that would only consist of the
checksum of the deleted blocks. Only when the scanner runs does it actually
update the real checksum with the live blocks.
##########
hadoop-hdds/container-service/src/main/java/org/apache/hadoop/ozone/container/checksum/ContainerChecksumTreeManager.java:
##########
@@ -256,6 +173,62 @@ private void
compareContainerMerkleTree(ContainerProtos.ContainerChecksumInfo th
}
private void compareBlockMerkleTree(ContainerProtos.BlockMerkleTree
thisBlockMerkleTree,
+ ContainerProtos.BlockMerkleTree peerBlockMerkleTree, ContainerDiffReport
report) {
+
+ boolean thisBlockDeleted = thisBlockMerkleTree.getDeleted();
+ boolean peerBlockDeleted = peerBlockMerkleTree.getDeleted();
+
+ if (thisBlockDeleted) {
+ // Our block has been deleted.
+ if (peerBlockDeleted && compareDataChecksums(thisBlockMerkleTree,
peerBlockMerkleTree) < 0) {
+ // If the peer's block is also deleted, use the largest checksum value
as the winner so that the values converge
+ // since there is no data corresponding to this block.
+ report.addDeletedBlock(peerBlockMerkleTree);
+ }
+ // Else, either the peer has not deleted the block or they have a lower
checksum for their deleted block.
+ // The peer needs to update their block.
+ } else {
+ if (peerBlockDeleted) {
+ // Our block has not yet been deleted, but peer's block has been.
+ // Mark our block as deleted to bring it in sync with the peer.
+ // Our block deleting service will eventually catch up.
+ // TODO HDDS-11765 Add support for deleting blocks from our replica
when a peer has already deleted the block.
+ report.addDeletedBlock(peerBlockMerkleTree);
+ } else {
+ // Neither our nor peer's block is deleted. Walk the chunk list to
find differences.
+ compareChunkMerkleTrees(thisBlockMerkleTree, peerBlockMerkleTree,
report);
+ }
+ }
+ }
+
+ /**
+ * Compares the data checksums of two block merkle trees lexicographically
as big-endian binary strings.
+ */
+ private static int compareDataChecksums(ContainerProtos.BlockMerkleTree
tree1,
Review Comment:
Why not just use a simple long comparator for this?
##########
hadoop-hdds/container-service/src/main/java/org/apache/hadoop/ozone/container/checksum/ContainerMerkleTreeWriter.java:
##########
@@ -63,9 +64,13 @@ public
ContainerMerkleTreeWriter(ContainerProtos.ContainerMerkleTree fromTree) {
id2Block = new TreeMap<>();
for (ContainerProtos.BlockMerkleTree blockTree:
fromTree.getBlockMerkleTreeList()) {
long blockID = blockTree.getBlockID();
- addBlock(blockID);
+ if (blockTree.getDeleted()) {
+ setDeletedBlock(blockID, blockTree.getDataChecksum());
+ } else {
+ addBlock(blockID);
+ }
for (ContainerProtos.ChunkMerkleTree chunkTree:
blockTree.getChunkMerkleTreeList()) {
Review Comment:
This can be moved to the `else` block, as we don't need chunk information
for the deleted blocks
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
