zookeeper-server/src/main/java/org/apache/zookeeper/server/SnapshotComparer.java - zookeeper - 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.zookeeper.server;

 import java.io.File;
 import java.io.Serializable;
 import java.util.ArrayList;
 import java.util.Collections;
 import java.util.Comparator;
 import java.util.HashMap;
 import java.util.List;
 import java.util.Map;
 import java.util.Scanner;
 import java.util.zip.CheckedInputStream;
 import org.apache.commons.cli.CommandLine;
 import org.apache.commons.cli.DefaultParser;
 import org.apache.commons.cli.HelpFormatter;
 import org.apache.commons.cli.Option;
 import org.apache.commons.cli.Options;
 import org.apache.commons.cli.ParseException;
 import org.apache.jute.BinaryInputArchive;
 import org.apache.jute.InputArchive;
 import org.apache.zookeeper.server.persistence.FileSnap;
 import org.apache.zookeeper.server.persistence.SnapStream;
 import org.apache.zookeeper.util.ServiceUtils;

 /**
  * SnapshotComparer is a tool that loads and compares two snapshots with configurable threshold and various filters, and outputs information about the delta.
  * The delta includes specific znode paths added, updated, deleted comparing one snapshot to another.
  * It's useful in use cases that involve snapshot analysis, such as offline data consistency checking, and data trending analysis (e.g. what's growing under which zNode path during when).
  * Only outputs information about permanent nodes, ignoring both sessions and ephemeral nodes.
  */
 public class SnapshotComparer {
   private final Options options;
   private static final String leftOption = "left";
   private static final String rightOption = "right";
   private static final String byteThresholdOption = "bytes";
   private static final String nodeThresholdOption = "nodes";
   private static final String debugOption = "debug";
   private static final String interactiveOption = "interactive";

   @SuppressWarnings("static")
   private SnapshotComparer() {
     options = new Options();
     options.addOption(
         Option.builder("l")
             .hasArg()
             .required(true)
             .longOpt(leftOption)
             .desc("(Required) The left snapshot file.")
             .argName("LEFT")
             .type(File.class)
             .build());
     options.addOption(
         Option.builder("r")
             .hasArg()
             .required(true)
             .longOpt(rightOption)
             .desc("(Required) The right snapshot file.")
             .argName("RIGHT")
             .type(File.class)
             .build());
     options.addOption(
         Option.builder("b")
             .hasArg()
             .required(true)
             .longOpt(byteThresholdOption)
             .desc("(Required) The node data delta size threshold, in bytes, for printing the node.")
             .argName("BYTETHRESHOLD")
             .type(String.class)
             .build());
     options.addOption(
         Option.builder("n")
             .hasArg()
             .required(true)
             .longOpt(nodeThresholdOption)
             .desc("(Required) The descendant node delta size threshold, in nodes, for printing the node.")
             .argName("NODETHRESHOLD")
             .type(String.class)
             .build());
     options.addOption("d", debugOption, false, "Use debug output.");
     options.addOption("i", interactiveOption, false, "Enter interactive mode.");
   }

   private void usage() {
     HelpFormatter help = new HelpFormatter();

     help.printHelp(
         120,
         "java -cp <classPath> " + SnapshotComparer.class.getName(),
         "",
         options,
         "");
   }

   public static void main(String[] args) throws Exception {
     SnapshotComparer app = new SnapshotComparer();
     app.compareSnapshots(args);
   }

   private void compareSnapshots(String[] args) throws Exception {
     CommandLine parsedOptions;
     try {
       parsedOptions = new DefaultParser().parse(options, args);
     } catch (ParseException e) {
       System.err.println(e.getMessage());
       usage();
       ServiceUtils.requestSystemExit(ExitCode.INVALID_INVOCATION.getValue());
       return;
     }

     File left = (File) parsedOptions.getParsedOptionValue(leftOption);
     File right = (File) parsedOptions.getParsedOptionValue(rightOption);
     int byteThreshold = Integer.parseInt((String) parsedOptions.getParsedOptionValue(byteThresholdOption));
     int nodeThreshold = Integer.parseInt((String) parsedOptions.getParsedOptionValue(nodeThresholdOption));
     boolean debug = parsedOptions.hasOption(debugOption);
     boolean interactive = parsedOptions.hasOption(interactiveOption);
     System.out.println("Successfully parsed options!");
     TreeInfo leftTree = new TreeInfo(left);
     TreeInfo rightTree = new TreeInfo(right);

     System.out.println(leftTree.toString());
     System.out.println(rightTree.toString());

     compareTrees(leftTree, rightTree, byteThreshold, nodeThreshold, debug, interactive);
   }

   private static class TreeInfo {
     public static class TreeNode {
       final String label;
       final long size;
       final List<TreeNode> children;
       long descendantSize;
       long descendantCount;

       public static class AlphabeticComparator implements Comparator<TreeNode>, Serializable {
         private static final long serialVersionUID = 2601197766392565593L;

         public int compare(TreeNode left, TreeNode right) {
           if (left == right) {
             return 0;
           }
           if (left == null) {
             return -1;
           }
           if (right == null) {
             return 1;
           }
           return left.label.compareTo(right.label);
         }
       }

       public TreeNode(String label, long size) {
         this.label = label;
         this.size = size;
         this.children = new ArrayList<>();
       }

       void populateChildren(String path, DataTree dataTree, TreeInfo treeInfo) throws Exception {
         populateChildren(path, dataTree, treeInfo, 1);
       }

       void populateChildren(String path, DataTree dataTree, TreeInfo treeInfo, int currentDepth) throws Exception {
         List<String> childLabels = null;
         childLabels = dataTree.getChildren(path, null, null);

         if (childLabels != null && !childLabels.isEmpty()) {
           for (String childName : childLabels){
             String childPath = path + "/" + childName;
             DataNode childNode = dataTree.getNode(childPath);
             long size;
             synchronized (childNode) {
               size = childNode.data == null ? 0 : childNode.data.length;
             }
             TreeNode childTreeNode = new TreeNode(childPath, size);
             childTreeNode.populateChildren(childPath, dataTree, treeInfo, currentDepth + 1);
             children.add(childTreeNode);
           }
         }
         descendantSize = 0;
         descendantCount = 0;
         for (TreeNode child : children) {
           descendantSize += child.descendantSize;
           descendantCount += child.descendantCount;
         }
         descendantSize += this.size;
         descendantCount += this.children.size();

         treeInfo.registerNode(this, currentDepth);
       }
     }

     final TreeNode root;
     long count;
     List<ArrayList<TreeNode>> nodesAtDepths = new ArrayList<>();
     Map<String, TreeNode> nodesByName = new HashMap<>();

     TreeInfo(File snapshot) throws Exception {
       DataTree dataTree = getSnapshot(snapshot);

       count = 0;
       long beginning = System.nanoTime();
       DataNode root = dataTree.getNode("");
       long size = root.data == null ? 0 : root.data.length;
       this.root = new TreeNode("", size);
       // Construct TreeInfo tree from DataTree
       this.root.populateChildren("", dataTree, this);
       long end = System.nanoTime();

       System.out.println(String.format("Processed data tree in %f seconds",
           ((((double) end - beginning) / 1000000)) / 1000));
     }

     void registerNode(TreeNode node, int depth) {
       while (depth > nodesAtDepths.size()) {
         nodesAtDepths.add(new ArrayList<>());
       }
       nodesAtDepths.get(depth - 1).add(node);
       nodesByName.put(node.label, node);

       this.count++;
     }

     public String toString() {
       StringBuilder builder = new StringBuilder();
       builder.append(String.format("Node count: %d%n", count));
       builder.append(String.format("Total size: %d%n", root.descendantSize));
       builder.append(String.format("Max depth: %d%n", nodesAtDepths.size()));
       for (int i = 0; i < nodesAtDepths.size(); i++) {
         builder.append(String.format("Count of nodes at depth %d: %d%n", i, nodesAtDepths.get(i).size()));
       }
       return builder.toString();
     }

     public static Comparator<TreeNode> MakeAlphabeticComparator() {
       return new TreeNode.AlphabeticComparator();
     }
   }

   /**
    * Parse a Zookeeper snapshot file to DataTree
    * @param file the snapshot file
    * @throws Exception
    */
   private static DataTree getSnapshot(File file) throws Exception {
     DataTree dataTree = new DataTree();
     Map<Long, Integer> sessions = new HashMap<>();
     CheckedInputStream snapIS = SnapStream.getInputStream(file);

     long beginning = System.nanoTime();
     InputArchive ia = BinaryInputArchive.getArchive(snapIS);
     FileSnap.deserialize(dataTree, sessions, ia);
     long end = System.nanoTime();
     System.out.println(String.format("Deserialized snapshot in %s in %f seconds", file.getName(),
         (((double) (end - beginning) / 1000000)) / 1000));
     return dataTree;
   }

   private static void printThresholdInfo(int byteThreshold, int nodeThreshold) {
     System.out.println(String.format("Printing analysis for nodes difference larger than %d bytes or node count difference larger than %d.", byteThreshold, nodeThreshold));
   }

   private static void compareTrees(TreeInfo left, TreeInfo right, int byteThreshold, int nodeThreshold, boolean debug, boolean interactive) {
     int maxDepth = Math.max(left.nodesAtDepths.size(), right.nodesAtDepths.size());

     if (!interactive) {
       printThresholdInfo(byteThreshold, nodeThreshold);
       for (int i = 0; i < maxDepth; i++) {
         System.out.println(String.format("Analysis for depth %d", i));
         compareLine(left, right, i, byteThreshold, nodeThreshold, debug, interactive);
       }
     } else {
       // interactive mode
       Scanner scanner = new Scanner(System.in);
       int currentDepth = 0;
       while (currentDepth < maxDepth) {
         System.out.println(String.format("Current depth is %d", currentDepth));
         System.out.println("- Press enter to move to print current depth layer;\n- Type a number to jump to and print all nodes at a given depth;\n- Enter an ABSOLUTE path to print the immediate subtree of a node. Path must start with '/'.");
         String input = scanner.nextLine();
         printThresholdInfo(byteThreshold, nodeThreshold);
         if (input.isEmpty()) {
           // input is Enter
           System.out.println(String.format("Analysis for depth %d", currentDepth));
           compareLine(left, right, currentDepth, byteThreshold, nodeThreshold, debug, interactive);
           currentDepth++;
         } else {
           // input is a path
           if (input.startsWith("/")){
             System.out.println(String.format("Analysis for node %s", input));
             compareSubtree(left, right, input, byteThreshold, nodeThreshold, debug, interactive);
           } else {
             // input is a number
             try {
               int depth = Integer.parseInt(input);
               if (depth < 0 || depth >= maxDepth) {
                 System.out.println(String.format("Depth must be in range [%d, %d]", 0, maxDepth - 1));
                 continue;
               }
               currentDepth = depth;
               System.out.println(String.format("Analysis for depth %d", currentDepth));
               compareLine(left, right, currentDepth, byteThreshold, nodeThreshold, debug, interactive);
             } catch (NumberFormatException ex) {
               // input is invalid
               System.out.println(String.format("Input %s is not valid. Depth must be in range [%d, %d]. Path must be an absolute path which starts with '/'.", input, 0, maxDepth - 1));
             }
           }
         }
         System.out.println("");
       }
     }
     System.out.println("All layers compared.");
   }

   private static void compareSubtree(TreeInfo left, TreeInfo right, String path, int byteThreshold, int nodeThreshold, boolean debug, boolean interactive) {
     TreeInfo.TreeNode leftRoot = left.nodesByName.get(path);
     TreeInfo.TreeNode rightRoot = right.nodesByName.get(path);

     List<TreeInfo.TreeNode> leftList = leftRoot == null ? new ArrayList<TreeInfo.TreeNode>() : leftRoot.children;
     List<TreeInfo.TreeNode> rightList = rightRoot == null ? new ArrayList<TreeInfo.TreeNode>() : rightRoot.children;

     if (leftRoot == null && rightRoot == null) {
       System.out.println(String.format("Path %s is neither found in left tree nor right tree.", path));
     } else {
       compareNodes(leftList, rightList, byteThreshold, nodeThreshold, debug, interactive);
     }
   }

   /**
    * Compare left tree and right tree at the same depth.
    * @param left the left data tree
    * @param right the right data tree
    * @param depth the depth of the data tree to be compared at
    * @param byteThreshold the node data delta size threshold, in bytes, for printing the node
    * @param nodeThreshold the descendant node delta size threshold, in nodes, for printing the node
    * @param debug If true, print more detailed debug information
    * @param interactive If true, enter interactive mode
    */
   private static void compareLine(TreeInfo left, TreeInfo right, int depth, int byteThreshold, int nodeThreshold, boolean debug, boolean interactive) {
     List<TreeInfo.TreeNode> leftList = depth >= left.nodesAtDepths.size() ? new ArrayList<>() : left.nodesAtDepths.get(depth);
     List<TreeInfo.TreeNode> rightList = depth >= right.nodesAtDepths.size() ? new ArrayList<>() : right.nodesAtDepths.get(depth);

     compareNodes(leftList, rightList, byteThreshold, nodeThreshold, debug, interactive);
   }

   private static void compareNodes(List<TreeInfo.TreeNode> leftList, List<TreeInfo.TreeNode> rightList, int byteThreshold, int nodeThreshold, boolean debug, boolean interactive) {
     Comparator<TreeInfo.TreeNode> alphabeticComparator = TreeInfo.MakeAlphabeticComparator();
     Collections.sort(leftList, alphabeticComparator);
     Collections.sort(rightList, alphabeticComparator);

     int leftIndex = 0;
     int rightIndex = 0;

     boolean leftRemaining = leftList.size() > leftIndex;
     boolean rightRemaining = rightList.size() > rightIndex;
     while (leftRemaining || rightRemaining) {
       TreeInfo.TreeNode leftNode = null;
       if (leftRemaining) {
         leftNode = leftList.get(leftIndex);
       }

       TreeInfo.TreeNode rightNode = null;
       if (rightRemaining) {
         rightNode = rightList.get(rightIndex);
       }

       if (leftNode != null && rightNode != null) {
         if (debug) {
           System.out.println(String.format("Comparing %s to %s", leftNode.label, rightNode.label));
         }
         int result = leftNode.label.compareTo(rightNode.label);
         if (result < 0) {
           if (debug) {
             System.out.println("left is less");
           }
           printLeftOnly(leftNode, byteThreshold, nodeThreshold, debug, interactive);
           leftIndex++;
         } else if (result > 0) {
           if (debug) {
             System.out.println("right is less");
           }
           printRightOnly(rightNode, byteThreshold, nodeThreshold, debug, interactive);
           rightIndex++;
         } else {
           if (debug) {
             System.out.println("same");
           }
           printBoth(leftNode, rightNode, byteThreshold, nodeThreshold, debug, interactive);
           leftIndex++;
           rightIndex++;
         }
       } else if (leftNode != null) {
         printLeftOnly(leftNode, byteThreshold, nodeThreshold, debug, interactive);
         leftIndex++;
       } else {
         printRightOnly(rightNode, byteThreshold, nodeThreshold, debug, interactive);
         rightIndex++;
       }

       leftRemaining = leftList.size() > leftIndex;
       rightRemaining = rightList.size() > rightIndex;
     }
   }

   static void printLeftOnly(TreeInfo.TreeNode node, int byteThreshold, int nodeThreshold, boolean debug, boolean interactive) {
     if (node.descendantSize > byteThreshold || node.descendantCount > nodeThreshold) {
       StringBuilder builder = new StringBuilder();
       builder.append(String.format("Node %s found only in left tree. ", node.label));
       printNode(node, builder);
       System.out.println(builder.toString());
     } else if (debug || interactive) {
       System.out.println(String.format("Filtered left node %s of size %d", node.label, node.descendantSize));
     }
   }

   static void printRightOnly(TreeInfo.TreeNode node, int byteThreshold, int nodeThreshold, boolean debug, boolean interactive) {
     if (node.descendantSize > byteThreshold || node.descendantCount > nodeThreshold) {
       StringBuilder builder = new StringBuilder();
       builder.append(String.format("Node %s found only in right tree. ", node.label));
       printNode(node, builder);
       System.out.println(builder.toString());
     } else if (debug || interactive) {
       System.out.println(String.format("Filtered right node %s of size %d", node.label, node.descendantSize));
     }
   }

   static void printBoth(TreeInfo.TreeNode leftNode, TreeInfo.TreeNode rightNode, int byteThreshold, int nodeThreshold, boolean debug, boolean interactive) {
     if (Math.abs(rightNode.descendantSize - leftNode.descendantSize) > byteThreshold
         || Math.abs(rightNode.descendantCount - leftNode.descendantCount) > nodeThreshold) {
       System.out.println(String.format(
           "Node %s found in both trees. Delta: %d bytes, %d descendants",
           leftNode.label,
           rightNode.descendantSize - leftNode.descendantSize,
           rightNode.descendantCount - leftNode.descendantCount));
     } else if (debug || interactive) {
       System.out.println(String.format("Filtered node %s of left size %d, right size %d", leftNode.label, leftNode.descendantSize, rightNode.descendantSize));
     }
   }

   static void printNode(TreeInfo.TreeNode node, StringBuilder builder) {
     builder.append(String.format("Descendant size: %d. Descendant count: %d", node.descendantSize, node.descendantCount));
   }
 }
	/**
	* 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.zookeeper.server;

	import java.io.File;
	import java.io.Serializable;
	import java.util.ArrayList;
	import java.util.Collections;
	import java.util.Comparator;
	import java.util.HashMap;
	import java.util.List;
	import java.util.Map;
	import java.util.Scanner;
	import java.util.zip.CheckedInputStream;
	import org.apache.commons.cli.CommandLine;
	import org.apache.commons.cli.DefaultParser;
	import org.apache.commons.cli.HelpFormatter;
	import org.apache.commons.cli.Option;
	import org.apache.commons.cli.Options;
	import org.apache.commons.cli.ParseException;
	import org.apache.jute.BinaryInputArchive;
	import org.apache.jute.InputArchive;
	import org.apache.zookeeper.server.persistence.FileSnap;
	import org.apache.zookeeper.server.persistence.SnapStream;
	import org.apache.zookeeper.util.ServiceUtils;

	/**
	* SnapshotComparer is a tool that loads and compares two snapshots with configurable threshold and various filters, and outputs information about the delta.
	* The delta includes specific znode paths added, updated, deleted comparing one snapshot to another.
	* It's useful in use cases that involve snapshot analysis, such as offline data consistency checking, and data trending analysis (e.g. what's growing under which zNode path during when).
	* Only outputs information about permanent nodes, ignoring both sessions and ephemeral nodes.
	*/
	public class SnapshotComparer {
	private final Options options;
	private static final String leftOption = "left";
	private static final String rightOption = "right";
	private static final String byteThresholdOption = "bytes";
	private static final String nodeThresholdOption = "nodes";
	private static final String debugOption = "debug";
	private static final String interactiveOption = "interactive";

	@SuppressWarnings("static")
	private SnapshotComparer() {
	options = new Options();
	options.addOption(
	Option.builder("l")
	.hasArg()
	.required(true)
	.longOpt(leftOption)
	.desc("(Required) The left snapshot file.")
	.argName("LEFT")
	.type(File.class)
	.build());
	options.addOption(
	Option.builder("r")
	.hasArg()
	.required(true)
	.longOpt(rightOption)
	.desc("(Required) The right snapshot file.")
	.argName("RIGHT")
	.type(File.class)
	.build());
	options.addOption(
	Option.builder("b")
	.hasArg()
	.required(true)
	.longOpt(byteThresholdOption)
	.desc("(Required) The node data delta size threshold, in bytes, for printing the node.")
	.argName("BYTETHRESHOLD")
	.type(String.class)
	.build());
	options.addOption(
	Option.builder("n")
	.hasArg()
	.required(true)
	.longOpt(nodeThresholdOption)
	.desc("(Required) The descendant node delta size threshold, in nodes, for printing the node.")
	.argName("NODETHRESHOLD")
	.type(String.class)
	.build());
	options.addOption("d", debugOption, false, "Use debug output.");
	options.addOption("i", interactiveOption, false, "Enter interactive mode.");
	}

	private void usage() {
	HelpFormatter help = new HelpFormatter();

	help.printHelp(
	120,
	"java -cp <classPath> " + SnapshotComparer.class.getName(),
	"",
	options,
	"");
	}

	public static void main(String[] args) throws Exception {
	SnapshotComparer app = new SnapshotComparer();
	app.compareSnapshots(args);
	}

	private void compareSnapshots(String[] args) throws Exception {
	CommandLine parsedOptions;
	try {
	parsedOptions = new DefaultParser().parse(options, args);
	} catch (ParseException e) {
	System.err.println(e.getMessage());
	usage();
	ServiceUtils.requestSystemExit(ExitCode.INVALID_INVOCATION.getValue());
	return;
	}

	File left = (File) parsedOptions.getParsedOptionValue(leftOption);
	File right = (File) parsedOptions.getParsedOptionValue(rightOption);
	int byteThreshold = Integer.parseInt((String) parsedOptions.getParsedOptionValue(byteThresholdOption));
	int nodeThreshold = Integer.parseInt((String) parsedOptions.getParsedOptionValue(nodeThresholdOption));
	boolean debug = parsedOptions.hasOption(debugOption);
	boolean interactive = parsedOptions.hasOption(interactiveOption);
	System.out.println("Successfully parsed options!");
	TreeInfo leftTree = new TreeInfo(left);
	TreeInfo rightTree = new TreeInfo(right);

	System.out.println(leftTree.toString());
	System.out.println(rightTree.toString());

	compareTrees(leftTree, rightTree, byteThreshold, nodeThreshold, debug, interactive);
	}

	private static class TreeInfo {
	public static class TreeNode {
	final String label;
	final long size;
	final List<TreeNode> children;
	long descendantSize;
	long descendantCount;

	public static class AlphabeticComparator implements Comparator<TreeNode>, Serializable {
	private static final long serialVersionUID = 2601197766392565593L;

	public int compare(TreeNode left, TreeNode right) {
	if (left == right) {
	return 0;
	}
	if (left == null) {
	return -1;
	}
	if (right == null) {
	return 1;
	}
	return left.label.compareTo(right.label);
	}
	}

	public TreeNode(String label, long size) {
	this.label = label;
	this.size = size;
	this.children = new ArrayList<>();
	}

	void populateChildren(String path, DataTree dataTree, TreeInfo treeInfo) throws Exception {
	populateChildren(path, dataTree, treeInfo, 1);
	}

	void populateChildren(String path, DataTree dataTree, TreeInfo treeInfo, int currentDepth) throws Exception {
	List<String> childLabels = null;
	childLabels = dataTree.getChildren(path, null, null);

	if (childLabels != null && !childLabels.isEmpty()) {
	for (String childName : childLabels){
	String childPath = path + "/" + childName;
	DataNode childNode = dataTree.getNode(childPath);
	long size;
	synchronized (childNode) {
	size = childNode.data == null ? 0 : childNode.data.length;
	}
	TreeNode childTreeNode = new TreeNode(childPath, size);
	childTreeNode.populateChildren(childPath, dataTree, treeInfo, currentDepth + 1);
	children.add(childTreeNode);
	}
	}
	descendantSize = 0;
	descendantCount = 0;
	for (TreeNode child : children) {
	descendantSize += child.descendantSize;
	descendantCount += child.descendantCount;
	}
	descendantSize += this.size;
	descendantCount += this.children.size();

	treeInfo.registerNode(this, currentDepth);
	}
	}

	final TreeNode root;
	long count;
	List<ArrayList<TreeNode>> nodesAtDepths = new ArrayList<>();
	Map<String, TreeNode> nodesByName = new HashMap<>();

	TreeInfo(File snapshot) throws Exception {
	DataTree dataTree = getSnapshot(snapshot);

	count = 0;
	long beginning = System.nanoTime();
	DataNode root = dataTree.getNode("");
	long size = root.data == null ? 0 : root.data.length;
	this.root = new TreeNode("", size);
	// Construct TreeInfo tree from DataTree
	this.root.populateChildren("", dataTree, this);
	long end = System.nanoTime();

	System.out.println(String.format("Processed data tree in %f seconds",
	((((double) end - beginning) / 1000000)) / 1000));
	}

	void registerNode(TreeNode node, int depth) {
	while (depth > nodesAtDepths.size()) {
	nodesAtDepths.add(new ArrayList<>());
	}
	nodesAtDepths.get(depth - 1).add(node);
	nodesByName.put(node.label, node);

	this.count++;
	}

	public String toString() {
	StringBuilder builder = new StringBuilder();
	builder.append(String.format("Node count: %d%n", count));
	builder.append(String.format("Total size: %d%n", root.descendantSize));
	builder.append(String.format("Max depth: %d%n", nodesAtDepths.size()));
	for (int i = 0; i < nodesAtDepths.size(); i++) {
	builder.append(String.format("Count of nodes at depth %d: %d%n", i, nodesAtDepths.get(i).size()));
	}
	return builder.toString();
	}

	public static Comparator<TreeNode> MakeAlphabeticComparator() {
	return new TreeNode.AlphabeticComparator();
	}
	}

	/**
	* Parse a Zookeeper snapshot file to DataTree
	* @param file the snapshot file
	* @throws Exception
	*/
	private static DataTree getSnapshot(File file) throws Exception {
	DataTree dataTree = new DataTree();
	Map<Long, Integer> sessions = new HashMap<>();
	CheckedInputStream snapIS = SnapStream.getInputStream(file);

	long beginning = System.nanoTime();
	InputArchive ia = BinaryInputArchive.getArchive(snapIS);
	FileSnap.deserialize(dataTree, sessions, ia);
	long end = System.nanoTime();
	System.out.println(String.format("Deserialized snapshot in %s in %f seconds", file.getName(),
	(((double) (end - beginning) / 1000000)) / 1000));
	return dataTree;
	}

	private static void printThresholdInfo(int byteThreshold, int nodeThreshold) {
	System.out.println(String.format("Printing analysis for nodes difference larger than %d bytes or node count difference larger than %d.", byteThreshold, nodeThreshold));
	}

	private static void compareTrees(TreeInfo left, TreeInfo right, int byteThreshold, int nodeThreshold, boolean debug, boolean interactive) {
	int maxDepth = Math.max(left.nodesAtDepths.size(), right.nodesAtDepths.size());

	if (!interactive) {
	printThresholdInfo(byteThreshold, nodeThreshold);
	for (int i = 0; i < maxDepth; i++) {
	System.out.println(String.format("Analysis for depth %d", i));
	compareLine(left, right, i, byteThreshold, nodeThreshold, debug, interactive);
	}
	} else {
	// interactive mode
	Scanner scanner = new Scanner(System.in);
	int currentDepth = 0;
	while (currentDepth < maxDepth) {
	System.out.println(String.format("Current depth is %d", currentDepth));
	System.out.println("- Press enter to move to print current depth layer;\n- Type a number to jump to and print all nodes at a given depth;\n- Enter an ABSOLUTE path to print the immediate subtree of a node. Path must start with '/'.");
	String input = scanner.nextLine();
	printThresholdInfo(byteThreshold, nodeThreshold);
	if (input.isEmpty()) {
	// input is Enter
	System.out.println(String.format("Analysis for depth %d", currentDepth));
	compareLine(left, right, currentDepth, byteThreshold, nodeThreshold, debug, interactive);
	currentDepth++;
	} else {
	// input is a path
	if (input.startsWith("/")){
	System.out.println(String.format("Analysis for node %s", input));
	compareSubtree(left, right, input, byteThreshold, nodeThreshold, debug, interactive);
	} else {
	// input is a number
	try {
	int depth = Integer.parseInt(input);
	if (depth < 0 \|\| depth >= maxDepth) {
	System.out.println(String.format("Depth must be in range [%d, %d]", 0, maxDepth - 1));
	continue;
	}
	currentDepth = depth;
	System.out.println(String.format("Analysis for depth %d", currentDepth));
	compareLine(left, right, currentDepth, byteThreshold, nodeThreshold, debug, interactive);
	} catch (NumberFormatException ex) {
	// input is invalid
	System.out.println(String.format("Input %s is not valid. Depth must be in range [%d, %d]. Path must be an absolute path which starts with '/'.", input, 0, maxDepth - 1));
	}
	}
	}
	System.out.println("");
	}
	}
	System.out.println("All layers compared.");
	}

	private static void compareSubtree(TreeInfo left, TreeInfo right, String path, int byteThreshold, int nodeThreshold, boolean debug, boolean interactive) {
	TreeInfo.TreeNode leftRoot = left.nodesByName.get(path);
	TreeInfo.TreeNode rightRoot = right.nodesByName.get(path);

	List<TreeInfo.TreeNode> leftList = leftRoot == null ? new ArrayList<TreeInfo.TreeNode>() : leftRoot.children;
	List<TreeInfo.TreeNode> rightList = rightRoot == null ? new ArrayList<TreeInfo.TreeNode>() : rightRoot.children;

	if (leftRoot == null && rightRoot == null) {
	System.out.println(String.format("Path %s is neither found in left tree nor right tree.", path));
	} else {
	compareNodes(leftList, rightList, byteThreshold, nodeThreshold, debug, interactive);
	}
	}

	/**
	* Compare left tree and right tree at the same depth.
	* @param left the left data tree
	* @param right the right data tree
	* @param depth the depth of the data tree to be compared at
	* @param byteThreshold the node data delta size threshold, in bytes, for printing the node
	* @param nodeThreshold the descendant node delta size threshold, in nodes, for printing the node
	* @param debug If true, print more detailed debug information
	* @param interactive If true, enter interactive mode
	*/
	private static void compareLine(TreeInfo left, TreeInfo right, int depth, int byteThreshold, int nodeThreshold, boolean debug, boolean interactive) {
	List<TreeInfo.TreeNode> leftList = depth >= left.nodesAtDepths.size() ? new ArrayList<>() : left.nodesAtDepths.get(depth);
	List<TreeInfo.TreeNode> rightList = depth >= right.nodesAtDepths.size() ? new ArrayList<>() : right.nodesAtDepths.get(depth);

	compareNodes(leftList, rightList, byteThreshold, nodeThreshold, debug, interactive);
	}

	private static void compareNodes(List<TreeInfo.TreeNode> leftList, List<TreeInfo.TreeNode> rightList, int byteThreshold, int nodeThreshold, boolean debug, boolean interactive) {
	Comparator<TreeInfo.TreeNode> alphabeticComparator = TreeInfo.MakeAlphabeticComparator();
	Collections.sort(leftList, alphabeticComparator);
	Collections.sort(rightList, alphabeticComparator);

	int leftIndex = 0;
	int rightIndex = 0;

	boolean leftRemaining = leftList.size() > leftIndex;
	boolean rightRemaining = rightList.size() > rightIndex;
	while (leftRemaining \|\| rightRemaining) {
	TreeInfo.TreeNode leftNode = null;
	if (leftRemaining) {
	leftNode = leftList.get(leftIndex);
	}

	TreeInfo.TreeNode rightNode = null;
	if (rightRemaining) {
	rightNode = rightList.get(rightIndex);
	}

	if (leftNode != null && rightNode != null) {
	if (debug) {
	System.out.println(String.format("Comparing %s to %s", leftNode.label, rightNode.label));
	}
	int result = leftNode.label.compareTo(rightNode.label);
	if (result < 0) {
	if (debug) {
	System.out.println("left is less");
	}
	printLeftOnly(leftNode, byteThreshold, nodeThreshold, debug, interactive);
	leftIndex++;
	} else if (result > 0) {
	if (debug) {
	System.out.println("right is less");
	}
	printRightOnly(rightNode, byteThreshold, nodeThreshold, debug, interactive);
	rightIndex++;
	} else {
	if (debug) {
	System.out.println("same");
	}
	printBoth(leftNode, rightNode, byteThreshold, nodeThreshold, debug, interactive);
	leftIndex++;
	rightIndex++;
	}
	} else if (leftNode != null) {
	printLeftOnly(leftNode, byteThreshold, nodeThreshold, debug, interactive);
	leftIndex++;
	} else {
	printRightOnly(rightNode, byteThreshold, nodeThreshold, debug, interactive);
	rightIndex++;
	}

	leftRemaining = leftList.size() > leftIndex;
	rightRemaining = rightList.size() > rightIndex;
	}
	}

	static void printLeftOnly(TreeInfo.TreeNode node, int byteThreshold, int nodeThreshold, boolean debug, boolean interactive) {
	if (node.descendantSize > byteThreshold \|\| node.descendantCount > nodeThreshold) {
	StringBuilder builder = new StringBuilder();
	builder.append(String.format("Node %s found only in left tree. ", node.label));
	printNode(node, builder);
	System.out.println(builder.toString());
	} else if (debug \|\| interactive) {
	System.out.println(String.format("Filtered left node %s of size %d", node.label, node.descendantSize));
	}
	}

	static void printRightOnly(TreeInfo.TreeNode node, int byteThreshold, int nodeThreshold, boolean debug, boolean interactive) {
	if (node.descendantSize > byteThreshold \|\| node.descendantCount > nodeThreshold) {
	StringBuilder builder = new StringBuilder();
	builder.append(String.format("Node %s found only in right tree. ", node.label));
	printNode(node, builder);
	System.out.println(builder.toString());
	} else if (debug \|\| interactive) {
	System.out.println(String.format("Filtered right node %s of size %d", node.label, node.descendantSize));
	}
	}

	static void printBoth(TreeInfo.TreeNode leftNode, TreeInfo.TreeNode rightNode, int byteThreshold, int nodeThreshold, boolean debug, boolean interactive) {
	if (Math.abs(rightNode.descendantSize - leftNode.descendantSize) > byteThreshold
	\|\| Math.abs(rightNode.descendantCount - leftNode.descendantCount) > nodeThreshold) {
	System.out.println(String.format(
	"Node %s found in both trees. Delta: %d bytes, %d descendants",
	leftNode.label,
	rightNode.descendantSize - leftNode.descendantSize,
	rightNode.descendantCount - leftNode.descendantCount));
	} else if (debug \|\| interactive) {
	System.out.println(String.format("Filtered node %s of left size %d, right size %d", leftNode.label, leftNode.descendantSize, rightNode.descendantSize));
	}
	}

	static void printNode(TreeInfo.TreeNode node, StringBuilder builder) {
	builder.append(String.format("Descendant size: %d. Descendant count: %d", node.descendantSize, node.descendantCount));
	}
	}