pastryregrtest.java

pastry的java实现的2.0b版

       */
      public DistComp(Id id) {
        this.id = id;
      }

      /**
       * DESCRIBE THE METHOD
       *
       * @param o1 DESCRIBE THE PARAMETER
       * @param o2 DESCRIBE THE PARAMETER
       * @return DESCRIBE THE RETURN VALUE
       */
      public int compare(Object o1, Object o2) {
        Id nid1 = (Id) o1;
        Id nid2 = (Id) o2;
        return nid1.distance(id).compareTo(nid2.distance(id));
      }
    }

    for (int k = -ls.ccwSize(); k <= ls.cwSize(); k++) {
      // for each id in the leafset
      Id id = ls.get(k).getNodeId();
      TreeSet distanceSet = new TreeSet(new DistComp(id));

      // compute a representation of the leafset, sorted by distance from the id
      for (int i = -ls.ccwSize(); i <= ls.cwSize(); i++) {
        NodeHandle nh = ls.get(i);
        distanceSet.add(nh.getNodeId());
      }

      int expectedSize = distanceSet.headSet(ls.get(-ls.ccwSize()).getNodeId())
        .size() + 1;
      int expectedSize1 = distanceSet.headSet(ls.get(ls.cwSize()).getNodeId())
        .size() + 1;
      if (expectedSize1 < expectedSize) {
        expectedSize = expectedSize1;
      }
      if (ls.overlaps()) {
        expectedSize = distanceSet.size();
      }

      NodeSet rs = ls.replicaSet(id, expectedSize);
      // now verify the replicaSet
      for (int i = 0; i < rs.size(); i++) {
        NodeHandle nh = rs.get(i);
        Id nid = nh.getNodeId();
        int inBetween = distanceSet.subSet(id, nid).size();

        if (inBetween != i) {
          System.out.println("checkLeafSet: replicaSet failure at"
            + rta.getNodeId() + " i=" + i + " k=" + k + " inBetween="
            + inBetween + "\n" + rs + "\n" + ls);
        }
      }

      // check size
      if (rs.size() != expectedSize) {
        System.out.println("checkLeafSet: replicaSet size failure at "
          + rta.getNodeId() + " k=" + k + " expectedSize=" + expectedSize
          + " " + "\n" + rs + "\n" + ls + " distanceSet:" + distanceSet);
      }

      // now check the range method
      int maxRank;
      if (ls.overlaps() || ls.size() == 0) {
        maxRank = rs.size() - 1;
      } else {
        maxRank = (k > 0) ? (ls.cwSize() - k - 1) : (ls.ccwSize() + k - 1);
      }

      int nearestPos;
      Id nearest = null;

      for (int j = -1; j <= maxRank * 2 + 1; j++) {
        IdRange range = null;

        if (j < 0) {
          // check the cumulative range
          try {
            range = rta.range(ls.get(k), maxRank, nearest, true);
          } catch (IllegalArgumentException iae) {
          } catch (RangeCannotBeDeterminedException rcbde) {
          }
        } else {
          // check the individual rank ranges
          try {
            range = rta.range(ls.get(k), j / 2, nearest, false);
          } catch (RangeCannotBeDeterminedException rcbde) {
          }
        }

        //System.out.println("j=" + j + " maxRank=" + maxRank + " " + range);

        //if ( (range != null) != (rs.size() >= 1) ) {
        if (range == null) {
          if (maxRank >= 0) {
            System.out.println("checkLeafSet: range size failure at "
              + rta.getNodeId() + " k=" + k + " maxRank=" + maxRank + "\n"
              + rs + "\n" + ls);
          }
          continue;
        }

        //nearestPos = ls.mostSimilar(range.getCCW());
        //nearest = ls.get(nearestPos).getNodeId();
        nearest = ls.get(k).getNodeId();
        nearestPos = k;

        // fetch the replicaSet of the key at the ccw edge of the range
        NodeSet cs = ls.replicaSet(range.getCCW(), maxRank + 1);

        if ((j >= 0 && cs.get(j / 2) == null)
          || (j >= 0 && !cs.get(j / 2).getNodeId().equals(nearest))
          || (j < 0 && !ls.overlaps() && !cs.get(maxRank).getNodeId().equals(
          nearest)) || (j < 0 && ls.overlaps() && !range.isFull())) {
          System.out.println("checkLeafSet: range failure 1 at "
            + rta.getNodeId() + " k=" + k + " j=" + j + " maxRank=" + maxRank
            + "\n" + cs + "\n" + ls + "\n" + range + "\nnearest=" + nearest);

          System.out.println("dist(nearest)="
            + nearest.distance(range.getCCW()));
          if (ls.get(nearestPos - 1) != null) {
            System.out.println("dist(nearest-1)="
              + ls.get(nearestPos - 1).getNodeId().distance(range.getCCW()));
          }
          if (ls.get(nearestPos + 1) != null) {
            System.out.println("dist(nearest+1)="
              + ls.get(nearestPos + 1).getNodeId().distance(range.getCCW()));
          }
        }

        //nearestPos = ls.mostSimilar(range.getCW());
        //nearest = ls.get(nearestPos).getNodeId();

        // fetch the replicaSet of the key at the cw edge of the range
        cs = ls.replicaSet(range.getCW().getCCW(), maxRank + 1);

        if ((j >= 0 && cs.get(j / 2) == null)
          || (j >= 0 && !cs.get(j / 2).getNodeId().equals(nearest))
          || (j < 0 && !ls.overlaps() && !cs.get(maxRank).getNodeId().equals(
          nearest)) || (j < 0 && ls.overlaps() && !range.isFull())) {
          System.out.println("checkLeafSet: range failure 2 at "
            + rta.getNodeId() + " k=" + k + " j=" + j + " maxRank=" + maxRank
            + "\n" + cs + "\n" + ls + "\n" + range + "\nnearest=" + nearest);

          System.out.println("dist(nearest)=" + nearest.distance(range.getCW()));
          if (ls.get(nearestPos - 1) != null) {
            System.out.println("dist(nearest-1)="
              + ls.get(nearestPos - 1).getNodeId().distance(range.getCW()));
          }
          if (ls.get(nearestPos + 1) != null) {
            System.out.println("dist(nearest+1)="
              + ls.get(nearestPos + 1).getNodeId().distance(range.getCW()));
          }
        }

        nearest = range.getCW();

      }

    }

  }

  /**
   * verify the correctness of the routing table
   *
   * @param rta DESCRIBE THE PARAMETER
   */

  private void checkRoutingTable(final RegrTestApp rta) {
    RoutingTable rt = rta.getRoutingTable();

    // check routing table

    for (int i = rt.numRows() - 1; i >= 0; i--) {
      // next row
      for (int j = 0; j < rt.numColumns(); j++) {
        // next column

        // skip if local Id digit
        // if (j == rta.getNodeId().getDigit(i,rt.baseBitLength())) continue;

        final RouteSet rs = rt.getRouteSet(i, j);

        Id domainFirst = rta.getNodeId().getDomainPrefix(i, j, 0,
          rt.baseBitLength());
        Id domainLast = rta.getNodeId().getDomainPrefix(i, j, -1,
          rt.baseBitLength());
        //System.out.println("prefixes " + rta.getNodeId() + domainFirst +
        // domainLast
        //	   + "compareTo=" + domainFirst.compareTo(domainLast));

        if (rs == null || rs.size() == 0) {
          // no entry

          // check if no nodes with appropriate prefix exist
          int inBetween = pastryNodesSorted.subMap(domainFirst, domainLast)
            .size()
            + (pastryNodesSorted.containsKey(domainLast) ? 1 : 0);

          if (inBetween > 0) {

            System.out.println("checkRoutingTable: missing RT entry at"
              + rta.getNodeId() + "row=" + i + " column=" + j + " inBetween="
              + inBetween);
            //System.out.println("prefixes " + rta.getNodeId() + domainFirst +
            // domainLast);
          }
        } else {
          // check entries
          NodeHandle nh;
          if (!environment.getSelectorManager().isSelectorThread() && (this instanceof DirectPastryRegrTest)) {
            // check if closest entry has valid proximity
            ExternalRunnable er =
              new ExternalRunnable() {
                protected Object execute() throws Exception {
                  DirectPastryNode temp = DirectPastryNode.currentNode;
                  DirectPastryNode.currentNode = (DirectPastryNode) rta.getPastryNode();
                  Object ret = rs.closestNode();
                  DirectPastryNode.currentNode = temp;
                  return ret;
                }
              };
            try {
              nh = (NodeHandle) er.invoke(environment);
            } catch (Exception e) {
              e.printStackTrace();
              System.exit(0);
              return;
            }
          } else {
            nh = (NodeHandle) rs.closestNode();
          }


          int bestProximity = Integer.MAX_VALUE;
          if (nh != null) {
            bestProximity = nh.proximity();
            if (nh.proximity() == Integer.MAX_VALUE) {
              System.out.println("checkRoutingTable failure 0, row=" + i
                + " column=" + j);
            }
          }

          for (int k = 0; k < rs.size(); k++) {

            // check for correct proximity ordering
            if (rs.get(k).isAlive() && rs.get(k).proximity() < bestProximity) {
              System.out.println("checkRoutingTable failure 1, row=" + i
                + " column=" + j + " rank=" + k);

            }

            NodeHandle nh2 = rs.get(k);
            Id id = nh2.getNodeId();

            // check if node exists
            if (!pastryNodesSorted.containsKey(id)) {
              if (isReallyAlive(nh2)) {
                System.out.println("checkRoutingTable failure 2, row=" + i
                  + " column=" + j + " rank=" + k);
              }
            } else
            // check if node has correct prefix
            if (!pastryNodesSorted.subMap(domainFirst, domainLast).containsKey(
              id)
              && !domainLast.equals(id)) {
              System.out.println("checkRoutingTable failure 3, row=" + i
                + " column=" + j + " rank=" + k);
            }
          }
        }
      }
    }

    //System.out.println(rt);

  }

  /**
   * initiate leafset maintenance
   */
  private void initiateLeafSetMaintenance() {

    for (int i = 0; i < pastryNodes.size(); i++) {
      PastryNode pn = (PastryNode) pastryNodes.get(i);
      pn.receiveMessage(new InitiateLeafSetMaintenance());
      while (simulate()) {
        ;
      }
    }

  }

  /**
   * initiate routing table maintenance
   */
  private void initiateRouteSetMaintenance() {

    for (int i = 0; i < pastryNodes.size(); i++) {
      PastryNode pn = (PastryNode) pastryNodes.get(i);
      pn.receiveMessage(new InitiateRouteSetMaintenance());
      while (simulate()) {
        ;
      }
    }

  }

  /**
   * kill a given number of nodes, randomly chosen
   *
   * @param num the number of nodes to kill
   */

  private void killNodes(int num) {
    for (int i = 0; i < num; i++) {
      int n = environment.getRandomSource().nextInt(pastryNodes.size());

      PastryNode pn = (PastryNode) pastryNodes.get(n);
      pastryNodes.remove(n);
      rtApps.remove(n);
      pastryNodesSorted.remove(pn.getNodeId());
      killNode(pn);
      System.out.println("Killed " + pn.getNodeId());
    }
  }

  /**
   * main
   *
   * @param pt DESCRIBE THE PARAMETER
   * @param args DESCRIBE THE PARAMETER
   * @param n DESCRIBE THE PARAMETER
   * @param d DESCRIBE THE PARAMETER
   * @param k DESCRIBE THE PARAMETER
   * @param m DESCRIBE THE PARAMETER
   * @param numConcJoins DESCRIBE THE PARAMETER
   */

  protected static void mainfunc(PastryRegrTest pt, String args[], int n,
                                 int d, int k, int m, int numConcJoins) {

    Date old = new Date();

    while (pt.pastryNodes.size() < n) {
      //for (int i=0; i<n; i += numConcJoins) {
      int remaining = n - pt.pastryNodes.size();
      if (remaining > numConcJoins) {
        remaining = numConcJoins;
      }

      pt.makePastryNode(remaining);

      if (pt.pastryNodes.size() % m == 0) {
        //if ((i + numConcJoins) % m == 0) {
        Date now = new Date();
        System.out.println(pt.pastryNodes.size() + " "
          + (now.getTime() - old.getTime()));
        // + " " + pt.msgCount);
//        pt.msgCount = 0;
        old = now;
      }

      pt.sendPings(k);
    }

    System.out.println(pt.pastryNodes.size() + " nodes constructed");

    System.out.println("starting RT and leafset check");
    // check all routing tables, leaf sets
    for (int j = 0; j < pt.rtApps.size(); j++) {
      pt.checkLeafSet((RegrTestApp) pt.rtApps.get(j));
      pt.checkRoutingTable((RegrTestApp) pt.rtApps.get(j));
    }
    System.out.println("finished RT and leafset check");

    // kill some nodes
    pt.killNodes(d);

    System.out.println(d + " nodes killed");

    // send messages
    pt.sendPings((n - d) * k);
    System.out.println((n - d) * k + " messages sent");

    System.out.println("starting leafset/RT maintenance");

    // initiate maint.
    pt.initiateLeafSetMaintenance();
    pt.initiateRouteSetMaintenance();

    System.out.println("finished leafset/RT maintenance");

    // send messages
    pt.sendPings((n - d) * k);
    System.out.println((n - d) * k + " messages sent");

    // Dist: wait until everyone detects failed nodes
    pt.pause(5000);

    // print all nodeIds, sorted
    //Iterator it = pt.pastryNodesSorted.keySet().iterator();
    //while (it.hasNext())
    //System.out.println(it.next());

    System.out.println("starting RT and leafset check");

    // check all routing tables, leaf sets
    for (int i = 0; i < pt.rtApps.size(); i++) {
      pt.checkLeafSet((RegrTestApp) pt.rtApps.get(i));
      pt.checkRoutingTable((RegrTestApp) pt.rtApps.get(i));
    }

    //pt.sendPings(k);

    for (int i = 0; i < 4; i++) {

      System.out.println("Starting leafset/RT maintenance, round " + (i + 2));

      // initiate maint.
      pt.initiateLeafSetMaintenance();
      pt.initiateRouteSetMaintenance();

      System.out.println("finished leafset/RT maintenance, round " + (i + 2));

      // send messages
      pt.sendPings((n - d) * k);
      System.out.println((n - d) * k + " messages sent");

      System.out.println("starting RT and leafset check, round " + (i + 2));

      // check all routing tables, leaf sets
      for (int j = 0; j < pt.rtApps.size(); j++) {
        pt.checkLeafSet((RegrTestApp) pt.rtApps.get(j));
        pt.checkRoutingTable((RegrTestApp) pt.rtApps.get(j));
      }

      pt.pause(1000);
    }

    pt.pause(5000);
    System.out.println("finished, exiting...");
    System.exit(0);
  }
}