hadoop-hdfs-project/hadoop-hdfs/src/main/java/org/apache/hadoop/hdfs/server/namenode/snapshot/SnapshotDiffInfo.java - hadoop - Git at Google

 /**
  * Licensed to the Apache Software Foundation (ASF) under one
  * or more contributor license agreements.  See the NOTICE file
  * distributed with this work for additional information
  * regarding copyright ownership.  The ASF licenses this file
  * to you under the Apache License, Version 2.0 (the
  * "License"); you may not use this file except in compliance
  * with the License.  You may obtain a copy of the License at
  *
  *     http://www.apache.org/licenses/LICENSE-2.0
  *
  * Unless required by applicable law or agreed to in writing, software
  * distributed under the License is distributed on an "AS IS" BASIS,
  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  * See the License for the specific language governing permissions and
  * limitations under the License.
  */
 package org.apache.hadoop.hdfs.server.namenode.snapshot;

 import java.util.Comparator;
 import java.util.HashMap;
 import java.util.List;
 import java.util.Map;
 import java.util.SortedMap;
 import java.util.TreeMap;

 import org.apache.hadoop.hdfs.protocol.SnapshotDiffReport;
 import org.apache.hadoop.hdfs.protocol.SnapshotDiffReport.DiffReportEntry;
 import org.apache.hadoop.hdfs.protocol.SnapshotDiffReport.DiffType;
 import org.apache.hadoop.hdfs.server.namenode.INode;
 import org.apache.hadoop.hdfs.server.namenode.INodeDirectory;
 import org.apache.hadoop.hdfs.server.namenode.INodeFile;
 import org.apache.hadoop.hdfs.server.namenode.INodeReference;
 import org.apache.hadoop.hdfs.server.namenode.snapshot.DirectoryWithSnapshotFeature.ChildrenDiff;

 import org.apache.hadoop.thirdparty.com.google.common.base.Preconditions;
 import org.apache.hadoop.thirdparty.com.google.common.primitives.SignedBytes;
 import org.apache.hadoop.util.ChunkedArrayList;

 /**
  * A class describing the difference between snapshots of a snapshottable
  * directory.
  */
 class SnapshotDiffInfo {
   /** Compare two inodes based on their full names */
   public static final Comparator<INode> INODE_COMPARATOR =
       new Comparator<INode>() {
     @Override
     public int compare(INode left, INode right) {
       if (left == null) {
         return right == null ? 0 : -1;
       } else {
         if (right == null) {
           return 1;
         } else {
           int cmp = compare(left.getParent(), right.getParent());
           return cmp == 0 ? SignedBytes.lexicographicalComparator().compare(
               left.getLocalNameBytes(), right.getLocalNameBytes()) : cmp;
         }
       }
     }
   };

   static class RenameEntry {
     private byte[][] sourcePath;
     private byte[][] targetPath;

     void setSource(INode source, byte[][] sourceParentPath) {
       Preconditions.checkState(sourcePath == null);
       sourcePath = new byte[sourceParentPath.length + 1][];
       System.arraycopy(sourceParentPath, 0, sourcePath, 0,
           sourceParentPath.length);
       sourcePath[sourcePath.length - 1] = source.getLocalNameBytes();
     }

     void setTarget(INode target, byte[][] targetParentPath) {
       targetPath = new byte[targetParentPath.length + 1][];
       System.arraycopy(targetParentPath, 0, targetPath, 0,
           targetParentPath.length);
       targetPath[targetPath.length - 1] = target.getLocalNameBytes();
     }

     void setTarget(byte[][] targetPath) {
       this.targetPath = targetPath;
     }

     boolean isRename() {
       return sourcePath != null && targetPath != null;
     }

     byte[][] getSourcePath() {
       return sourcePath;
     }

     byte[][] getTargetPath() {
       return targetPath;
     }
   }

   /** The root directory of the snapshots */
   private final INodeDirectory snapshotRoot;
   /**
    *  The scope directory under which snapshot diff is calculated.
    */
   private final INodeDirectory snapshotDiffScopeDir;
   /** The starting point of the difference */
   private final Snapshot from;
   /** The end point of the difference */
   private final Snapshot to;
   /**
    * A map recording modified INodeFile and INodeDirectory and their relative
    * path corresponding to the snapshot root. Sorted based on their names.
    */
   private final SortedMap<INode, byte[][]> diffMap =
       new TreeMap<INode, byte[][]>(INODE_COMPARATOR);
   /**
    * A map capturing the detailed difference about file creation/deletion.
    * Each key indicates a directory whose children have been changed between
    * the two snapshots, while its associated value is a {@link ChildrenDiff}
    * storing the changes (creation/deletion) happened to the children (files).
    */
   private final Map<INodeDirectory, ChildrenDiff> dirDiffMap =
       new HashMap<INodeDirectory, ChildrenDiff>();

   private final Map<Long, RenameEntry> renameMap =
       new HashMap<Long, RenameEntry>();

   // Total directories compared
   private long totalDirsCompared;

   // Total directories
   private long totalDirsProcessed;

   // Total files compared
   private long totalFilesCompared;

   // Total files
   private long totalFilesProcessed;

   // Total children listing time
   private long childrenListingTime;

   SnapshotDiffInfo(INodeDirectory snapshotRootDir,
       INodeDirectory snapshotDiffScopeDir, Snapshot start, Snapshot end) {
     Preconditions.checkArgument(snapshotRootDir.isSnapshottable() &&
         snapshotDiffScopeDir.isDescendantOfSnapshotRoot(snapshotRootDir));
     this.snapshotRoot = snapshotRootDir;
     this.snapshotDiffScopeDir = snapshotDiffScopeDir;
     this.from = start;
     this.to = end;
     this.totalDirsCompared = 0;
     this.totalDirsProcessed = 0;
     this.totalFilesCompared = 0;
     this.totalFilesProcessed = 0;
   }

   /** Add a dir-diff pair */
   void addDirDiff(INodeDirectory dir, byte[][] relativePath, ChildrenDiff diff) {
     dirDiffMap.put(dir, diff);
     diffMap.put(dir, relativePath);
     // detect rename
     for (INode created : diff.getCreatedUnmodifiable()) {
       if (created.isReference()) {
         RenameEntry entry = getEntry(created.getId());
         if (entry.getTargetPath() == null) {
           entry.setTarget(created, relativePath);
         }
       }
     }
     for (INode deleted : diff.getDeletedUnmodifiable()) {
       if (deleted instanceof INodeReference.WithName) {
         RenameEntry entry = getEntry(deleted.getId());
         entry.setSource(deleted, relativePath);
       }
     }
   }

   Snapshot getFrom() {
     return from;
   }

   Snapshot getTo() {
     return to;
   }


   void incrementDirsCompared() {
     this.totalDirsCompared++;
     incrementDirsProcessed();
   }

   void incrementDirsProcessed() {
     this.totalDirsProcessed++;
   }

   void incrementFilesCompared() {
     this.totalFilesCompared++;
     incrementFilesProcessed();
   }

   void incrementFilesProcessed() {
     this.totalFilesProcessed++;
   }

   public void addChildrenListingTime(long millis) {
     this.childrenListingTime += millis;
   }

   private RenameEntry getEntry(long inodeId) {
     RenameEntry entry = renameMap.get(inodeId);
     if (entry == null) {
       entry = new RenameEntry();
       renameMap.put(inodeId, entry);
     }
     return entry;
   }

   void setRenameTarget(long inodeId, byte[][] path) {
     getEntry(inodeId).setTarget(path);
   }

   /** Add a modified file */
   void addFileDiff(INodeFile file, byte[][] relativePath) {
     diffMap.put(file, relativePath);
   }

   /** @return True if {@link #from} is earlier than {@link #to} */
   boolean isFromEarlier() {
     return Snapshot.ID_COMPARATOR.compare(from, to) < 0;
   }

   /**
    * Generate a {@link SnapshotDiffReport} based on detailed diff information.
    * @return A {@link SnapshotDiffReport} describing the difference
    */
   public SnapshotDiffReport generateReport() {
     List<DiffReportEntry> diffReportList = new ChunkedArrayList<>();
     for (Map.Entry<INode,byte[][]> drEntry : diffMap.entrySet()) {
       INode node = drEntry.getKey();
       byte[][] path = drEntry.getValue();
       diffReportList.add(new DiffReportEntry(DiffType.MODIFY, path, null));
       if (node.isDirectory()) {
         List<DiffReportEntry> subList = generateReport(dirDiffMap.get(node),
             path, isFromEarlier(), renameMap);
         diffReportList.addAll(subList);
       }
     }

     SnapshotDiffReport.DiffStats dStats = new SnapshotDiffReport.DiffStats(
         this.totalDirsCompared, this.totalDirsProcessed,
         this.totalFilesCompared, this.totalFilesProcessed,
         this.childrenListingTime);

     return new SnapshotDiffReport(snapshotRoot.getFullPathName(),
         Snapshot.getSnapshotName(from), Snapshot.getSnapshotName(to),
         dStats, diffReportList);
   }

   /**
    * Interpret the ChildrenDiff and generate a list of {@link DiffReportEntry}.
    * @param dirDiff The ChildrenDiff.
    * @param parentPath The relative path of the parent.
    * @param fromEarlier True indicates {@code diff=later-earlier},
    *                    False indicates {@code diff=earlier-later}
    * @param renameMap A map containing information about rename operations.
    * @return A list of {@link DiffReportEntry} as the diff report.
    */
   private List<DiffReportEntry> generateReport(ChildrenDiff dirDiff,
       byte[][] parentPath, boolean fromEarlier, Map<Long, RenameEntry> renameMap) {
     List<DiffReportEntry> list = new ChunkedArrayList<>();
     byte[][] fullPath = new byte[parentPath.length + 1][];
     System.arraycopy(parentPath, 0, fullPath, 0, parentPath.length);
     for (INode cnode : dirDiff.getCreatedUnmodifiable()) {
       RenameEntry entry = renameMap.get(cnode.getId());
       if (entry == null || !entry.isRename()) {
         fullPath[fullPath.length - 1] = cnode.getLocalNameBytes();
         list.add(new DiffReportEntry(fromEarlier ? DiffType.CREATE
             : DiffType.DELETE, fullPath));
       }
     }
     for (INode dnode : dirDiff.getDeletedUnmodifiable()) {
       RenameEntry entry = renameMap.get(dnode.getId());
       if (entry != null && entry.isRename()) {
         list.add(new DiffReportEntry(DiffType.RENAME,
             fromEarlier ? entry.getSourcePath() : entry.getTargetPath(),
             fromEarlier ? entry.getTargetPath() : entry.getSourcePath()));
       } else {
         fullPath[fullPath.length - 1] = dnode.getLocalNameBytes();
         list.add(new DiffReportEntry(fromEarlier ? DiffType.DELETE
             : DiffType.CREATE, fullPath));
       }
     }
     return list;
   }
 }
	/**
	* Licensed to the Apache Software Foundation (ASF) under one
	* or more contributor license agreements. See the NOTICE file
	* distributed with this work for additional information
	* regarding copyright ownership. The ASF licenses this file
	* to you under the Apache License, Version 2.0 (the
	* "License"); you may not use this file except in compliance
	* with the License. You may obtain a copy of the License at
	*
	* http://www.apache.org/licenses/LICENSE-2.0
	*
	* Unless required by applicable law or agreed to in writing, software
	* distributed under the License is distributed on an "AS IS" BASIS,
	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	* See the License for the specific language governing permissions and
	* limitations under the License.
	*/
	package org.apache.hadoop.hdfs.server.namenode.snapshot;

	import java.util.Comparator;
	import java.util.HashMap;
	import java.util.List;
	import java.util.Map;
	import java.util.SortedMap;
	import java.util.TreeMap;

	import org.apache.hadoop.hdfs.protocol.SnapshotDiffReport;
	import org.apache.hadoop.hdfs.protocol.SnapshotDiffReport.DiffReportEntry;
	import org.apache.hadoop.hdfs.protocol.SnapshotDiffReport.DiffType;
	import org.apache.hadoop.hdfs.server.namenode.INode;
	import org.apache.hadoop.hdfs.server.namenode.INodeDirectory;
	import org.apache.hadoop.hdfs.server.namenode.INodeFile;
	import org.apache.hadoop.hdfs.server.namenode.INodeReference;
	import org.apache.hadoop.hdfs.server.namenode.snapshot.DirectoryWithSnapshotFeature.ChildrenDiff;

	import org.apache.hadoop.thirdparty.com.google.common.base.Preconditions;
	import org.apache.hadoop.thirdparty.com.google.common.primitives.SignedBytes;
	import org.apache.hadoop.util.ChunkedArrayList;

	/**
	* A class describing the difference between snapshots of a snapshottable
	* directory.
	*/
	class SnapshotDiffInfo {
	/** Compare two inodes based on their full names */
	public static final Comparator<INode> INODE_COMPARATOR =
	new Comparator<INode>() {
	@Override
	public int compare(INode left, INode right) {
	if (left == null) {
	return right == null ? 0 : -1;
	} else {
	if (right == null) {
	return 1;
	} else {
	int cmp = compare(left.getParent(), right.getParent());
	return cmp == 0 ? SignedBytes.lexicographicalComparator().compare(
	left.getLocalNameBytes(), right.getLocalNameBytes()) : cmp;
	}
	}
	}
	};

	static class RenameEntry {
	private byte[][] sourcePath;
	private byte[][] targetPath;

	void setSource(INode source, byte[][] sourceParentPath) {
	Preconditions.checkState(sourcePath == null);
	sourcePath = new byte[sourceParentPath.length + 1][];
	System.arraycopy(sourceParentPath, 0, sourcePath, 0,
	sourceParentPath.length);
	sourcePath[sourcePath.length - 1] = source.getLocalNameBytes();
	}

	void setTarget(INode target, byte[][] targetParentPath) {
	targetPath = new byte[targetParentPath.length + 1][];
	System.arraycopy(targetParentPath, 0, targetPath, 0,
	targetParentPath.length);
	targetPath[targetPath.length - 1] = target.getLocalNameBytes();
	}

	void setTarget(byte[][] targetPath) {
	this.targetPath = targetPath;
	}

	boolean isRename() {
	return sourcePath != null && targetPath != null;
	}

	byte[][] getSourcePath() {
	return sourcePath;
	}

	byte[][] getTargetPath() {
	return targetPath;
	}
	}

	/** The root directory of the snapshots */
	private final INodeDirectory snapshotRoot;
	/**
	* The scope directory under which snapshot diff is calculated.
	*/
	private final INodeDirectory snapshotDiffScopeDir;
	/** The starting point of the difference */
	private final Snapshot from;
	/** The end point of the difference */
	private final Snapshot to;
	/**
	* A map recording modified INodeFile and INodeDirectory and their relative
	* path corresponding to the snapshot root. Sorted based on their names.
	*/
	private final SortedMap<INode, byte[][]> diffMap =
	new TreeMap<INode, byte[][]>(INODE_COMPARATOR);
	/**
	* A map capturing the detailed difference about file creation/deletion.
	* Each key indicates a directory whose children have been changed between
	* the two snapshots, while its associated value is a {@link ChildrenDiff}
	* storing the changes (creation/deletion) happened to the children (files).
	*/
	private final Map<INodeDirectory, ChildrenDiff> dirDiffMap =
	new HashMap<INodeDirectory, ChildrenDiff>();

	private final Map<Long, RenameEntry> renameMap =
	new HashMap<Long, RenameEntry>();

	// Total directories compared
	private long totalDirsCompared;

	// Total directories
	private long totalDirsProcessed;

	// Total files compared
	private long totalFilesCompared;

	// Total files
	private long totalFilesProcessed;

	// Total children listing time
	private long childrenListingTime;

	SnapshotDiffInfo(INodeDirectory snapshotRootDir,
	INodeDirectory snapshotDiffScopeDir, Snapshot start, Snapshot end) {
	Preconditions.checkArgument(snapshotRootDir.isSnapshottable() &&
	snapshotDiffScopeDir.isDescendantOfSnapshotRoot(snapshotRootDir));
	this.snapshotRoot = snapshotRootDir;
	this.snapshotDiffScopeDir = snapshotDiffScopeDir;
	this.from = start;
	this.to = end;
	this.totalDirsCompared = 0;
	this.totalDirsProcessed = 0;
	this.totalFilesCompared = 0;
	this.totalFilesProcessed = 0;
	}

	/** Add a dir-diff pair */
	void addDirDiff(INodeDirectory dir, byte[][] relativePath, ChildrenDiff diff) {
	dirDiffMap.put(dir, diff);
	diffMap.put(dir, relativePath);
	// detect rename
	for (INode created : diff.getCreatedUnmodifiable()) {
	if (created.isReference()) {
	RenameEntry entry = getEntry(created.getId());
	if (entry.getTargetPath() == null) {
	entry.setTarget(created, relativePath);
	}
	}
	}
	for (INode deleted : diff.getDeletedUnmodifiable()) {
	if (deleted instanceof INodeReference.WithName) {
	RenameEntry entry = getEntry(deleted.getId());
	entry.setSource(deleted, relativePath);
	}
	}
	}

	Snapshot getFrom() {
	return from;
	}

	Snapshot getTo() {
	return to;
	}


	void incrementDirsCompared() {
	this.totalDirsCompared++;
	incrementDirsProcessed();
	}

	void incrementDirsProcessed() {
	this.totalDirsProcessed++;
	}

	void incrementFilesCompared() {
	this.totalFilesCompared++;
	incrementFilesProcessed();
	}

	void incrementFilesProcessed() {
	this.totalFilesProcessed++;
	}

	public void addChildrenListingTime(long millis) {
	this.childrenListingTime += millis;
	}

	private RenameEntry getEntry(long inodeId) {
	RenameEntry entry = renameMap.get(inodeId);
	if (entry == null) {
	entry = new RenameEntry();
	renameMap.put(inodeId, entry);
	}
	return entry;
	}

	void setRenameTarget(long inodeId, byte[][] path) {
	getEntry(inodeId).setTarget(path);
	}

	/** Add a modified file */
	void addFileDiff(INodeFile file, byte[][] relativePath) {
	diffMap.put(file, relativePath);
	}

	/** @return True if {@link #from} is earlier than {@link #to} */
	boolean isFromEarlier() {
	return Snapshot.ID_COMPARATOR.compare(from, to) < 0;
	}

	/**
	* Generate a {@link SnapshotDiffReport} based on detailed diff information.
	* @return A {@link SnapshotDiffReport} describing the difference
	*/
	public SnapshotDiffReport generateReport() {
	List<DiffReportEntry> diffReportList = new ChunkedArrayList<>();
	for (Map.Entry<INode,byte[][]> drEntry : diffMap.entrySet()) {
	INode node = drEntry.getKey();
	byte[][] path = drEntry.getValue();
	diffReportList.add(new DiffReportEntry(DiffType.MODIFY, path, null));
	if (node.isDirectory()) {
	List<DiffReportEntry> subList = generateReport(dirDiffMap.get(node),
	path, isFromEarlier(), renameMap);
	diffReportList.addAll(subList);
	}
	}

	SnapshotDiffReport.DiffStats dStats = new SnapshotDiffReport.DiffStats(
	this.totalDirsCompared, this.totalDirsProcessed,
	this.totalFilesCompared, this.totalFilesProcessed,
	this.childrenListingTime);

	return new SnapshotDiffReport(snapshotRoot.getFullPathName(),
	Snapshot.getSnapshotName(from), Snapshot.getSnapshotName(to),
	dStats, diffReportList);
	}

	/**
	* Interpret the ChildrenDiff and generate a list of {@link DiffReportEntry}.
	* @param dirDiff The ChildrenDiff.
	* @param parentPath The relative path of the parent.
	* @param fromEarlier True indicates {@code diff=later-earlier},
	* False indicates {@code diff=earlier-later}
	* @param renameMap A map containing information about rename operations.
	* @return A list of {@link DiffReportEntry} as the diff report.
	*/
	private List<DiffReportEntry> generateReport(ChildrenDiff dirDiff,
	byte[][] parentPath, boolean fromEarlier, Map<Long, RenameEntry> renameMap) {
	List<DiffReportEntry> list = new ChunkedArrayList<>();
	byte[][] fullPath = new byte[parentPath.length + 1][];
	System.arraycopy(parentPath, 0, fullPath, 0, parentPath.length);
	for (INode cnode : dirDiff.getCreatedUnmodifiable()) {
	RenameEntry entry = renameMap.get(cnode.getId());
	if (entry == null \|\| !entry.isRename()) {
	fullPath[fullPath.length - 1] = cnode.getLocalNameBytes();
	list.add(new DiffReportEntry(fromEarlier ? DiffType.CREATE
	: DiffType.DELETE, fullPath));
	}
	}
	for (INode dnode : dirDiff.getDeletedUnmodifiable()) {
	RenameEntry entry = renameMap.get(dnode.getId());
	if (entry != null && entry.isRename()) {
	list.add(new DiffReportEntry(DiffType.RENAME,
	fromEarlier ? entry.getSourcePath() : entry.getTargetPath(),
	fromEarlier ? entry.getTargetPath() : entry.getSourcePath()));
	} else {
	fullPath[fullPath.length - 1] = dnode.getLocalNameBytes();
	list.add(new DiffReportEntry(fromEarlier ? DiffType.DELETE
	: DiffType.CREATE, fullPath));
	}
	}
	return list;
	}
	}