path: root/zookeeper-server/src/main/java/org/apache/zookeeper/server/SnapshotComparer.java

/**
 * 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 {
    FileSnap fileSnap = new FileSnap(null);
    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));
  }
}