examples/deprecated/java/dht/chord/Node.java

   1 /* Copyright (c) 2006-2019. The SimGrid Team. All rights reserved.          */
   2
   3 /* This program is free software; you can redistribute it and/or modify it
   4  * under the terms of the license (GNU LGPL) which comes with this package. */
   5
   6 package dht.chord;
   7
   8 import org.simgrid.msg.Msg;
   9 import org.simgrid.msg.Comm;
  10 import org.simgrid.msg.Host;
  11 import org.simgrid.msg.Task;
  12 import org.simgrid.msg.Process;
  13 import org.simgrid.msg.MsgException;
  14 import org.simgrid.msg.TimeoutException;
  15 public class Node extends Process {
  16   protected int id;
  17   protected String mailbox;
  18   protected int predId;
  19   protected String predMailbox;
  20   protected int nextFingerToFix;
  21   protected Comm commReceive;
  22   ///Last time I changed a finger or my predecessor
  23   protected double lastChangeDate;
  24   private int[] fingers;
  25
  26   public Node(Host host, String name, String[] args) {
  27     super(host,name,args);
  28   }
  29
  30   @Override
  31   public void main(String[] args) throws MsgException {
  32     if (args.length != 2 && args.length != 4) {
  33       Msg.info("You need to provide 2 or 4 arguments.");
  34       return;
  35     }
  36     double initTime = Msg.getClock();
  37     int i;
  38     boolean joinSuccess;
  39     double deadline;
  40
  41     double nextStabilizeDate = initTime + Common.PERIODIC_STABILIZE_DELAY;
  42     double nextFixFingersDate = initTime + Common.PERIODIC_FIX_FINGERS_DELAY;
  43     double nextCheckPredecessorDate = initTime + Common.PERIODIC_CHECK_PREDECESSOR_DELAY;
  44     double nextLookupDate = initTime + Common.PERIODIC_LOOKUP_DELAY;
  45
  46     mailbox = args[0];
  47     id = Integer.parseInt(args[0]);
  48
  49     fingers = new int[Common.NB_BITS];
  50     for (i = 0; i < Common.NB_BITS; i++) {
  51       fingers[i] = -1;
  52       setFinger(i,this.id);
  53     }
  54
  55     //First node
  56     if (args.length == 2) {
  57       deadline = Integer.parseInt(args[1]);
  58       create();
  59       joinSuccess = true;
  60     } else {
  61       int knownId = Integer.parseInt(args[1]);
  62       deadline = Integer.parseInt(args[3]);
  63       Msg.debug("Hey! Let's join the system with the id " + id + ".");
  64
  65       joinSuccess = join(knownId);
  66     }
  67
  68     if (!joinSuccess) {
  69       Msg.info("I couldn't join the ring");
  70       return;
  71     }
  72
  73     double currentClock = Msg.getClock();
  74     while (currentClock < (initTime + deadline) && currentClock < Common.MAX_SIMULATION_TIME) {
  75       if (commReceive == null) {
  76         commReceive = Task.irecv(this.mailbox);
  77       }
  78       try {
  79         if (!commReceive.test()) {
  80           if (currentClock >= nextStabilizeDate) {
  81             stabilize();
  82             nextStabilizeDate = Msg.getClock() + Common.PERIODIC_STABILIZE_DELAY;
  83           } else if (currentClock >= nextFixFingersDate) {
  84             fixFingers();
  85             nextFixFingersDate = Msg.getClock() + Common.PERIODIC_FIX_FINGERS_DELAY;
  86           } else if (currentClock >= nextCheckPredecessorDate) {
  87             this.checkPredecessor();
  88             nextCheckPredecessorDate = Msg.getClock() + Common.PERIODIC_CHECK_PREDECESSOR_DELAY;
  89           } else if (currentClock >= nextLookupDate) {
  90             this.randomLookup();
  91             nextLookupDate = Msg.getClock() + Common.PERIODIC_LOOKUP_DELAY;
  92           } else {
  93             waitFor(5);
  94           }
  95           currentClock = Msg.getClock();
  96         } else {
  97           handleTask(commReceive.getTask());
  98           currentClock = Msg.getClock();
  99           commReceive = null;
 100         }
 101       }
 102       catch (Exception e) {
 103         currentClock = Msg.getClock();
 104         commReceive = null;
 105       }
 106     }
 107     leave();
 108     if (commReceive != null) {
 109       commReceive = null;
 110     }
 111   }
 112
 113   private void handleTask(Task task) {
 114     if (task instanceof FindSuccessorTask) {
 115       FindSuccessorTask fTask = (FindSuccessorTask)task;
 116       Msg.debug("Receiving a 'Find Successor' request from " + fTask.getIssuerHostName() + " for id " +
 117                 fTask.getRequestId());
 118       // is my successor the successor?
 119       if (isInInterval(fTask.getRequestId(), this.id + 1, fingers[0])) {
 120         Msg.debug("Send the request to " + fTask.getAnswerTo() + " with answer " + fingers[0]);
 121         FindSuccessorAnswerTask answer = new FindSuccessorAnswerTask(getHost().getName(), mailbox, fingers[0]);
 122         answer.dsend(fTask.getAnswerTo());
 123       } else {
 124         // otherwise, forward the request to the closest preceding finger in my table
 125         int closest = closestPrecedingNode(fTask.getRequestId());
 126         Msg.debug("Forward the request to " + closest);
 127         fTask.dsend(Integer.toString(closest));
 128       }
 129     } else if (task instanceof GetPredecessorTask) {
 130       GetPredecessorTask gTask = (GetPredecessorTask)(task);
 131       Msg.debug("Receiving a 'Get Predecessor' request from " + gTask.getIssuerHostName());
 132       GetPredecessorAnswerTask answer = new GetPredecessorAnswerTask(getHost().getName(), mailbox, predId);
 133       answer.dsend(gTask.getAnswerTo());
 134     } else if (task instanceof NotifyTask) {
 135       NotifyTask nTask = (NotifyTask)task;
 136       notify(nTask.getRequestId());
 137     } else {
 138       Msg.debug("Ignoring unexpected task of type:" + task);
 139     }
 140   }
 141
 142   private void leave() {
 143     Msg.debug("Well Guys! I Think it's time for me to quit ;)");
 144     // TODO: Notify my successor and predecessor.
 145   }
 146
 147   /** @brief Initializes the current node as the first one of the system  */
 148   private void create() {
 149     Msg.debug("Create a new Chord ring...");
 150     setPredecessor(-1);
 151   }
 152
 153   // Makes the current node join the ring, knowing the id of a node already in the ring
 154   private boolean join(int knownId) {
 155     Msg.info("Joining the ring with id " + this.id + " knowing node " + knownId);
 156     setPredecessor(-1);
 157     int successorId = remoteFindSuccessor(knownId, this.id);
 158     if (successorId == -1) {
 159       Msg.info("Cannot join the ring.");
 160     } else {
 161       setFinger(0, successorId);
 162     }
 163     return successorId != -1;
 164   }
 165
 166   private void setPredecessor(int predecessorId) {
 167     if (predecessorId != predId) {
 168       predId = predecessorId;
 169       if (predecessorId != -1) {
 170         predMailbox = Integer.toString(predId);
 171       }
 172       lastChangeDate = Msg.getClock();
 173     }
 174   }
 175
 176   /**
 177    * @brief Asks another node its predecessor.
 178    * @param askTo the node to ask to
 179    * @return the id of its predecessor node, or -1 if the request failed(or if the node does not know its predecessor)
 180    */
 181   private int remoteGetPredecessor(int askTo) {
 182     int predecessorId = -1;
 183     boolean stop = false;
 184     Msg.debug("Sending a 'Get Predecessor' request to " + askTo);
 185     String mailboxTo = Integer.toString(askTo);
 186     GetPredecessorTask sendTask = new GetPredecessorTask(getHost().getName(), this.mailbox);
 187     try {
 188       sendTask.send(mailboxTo, Common.TIMEOUT);
 189       do {
 190         if (commReceive == null) {
 191           commReceive = Task.irecv(this.mailbox);
 192         }
 193         commReceive.waitCompletion(Common.TIMEOUT);
 194         Task taskReceived = commReceive.getTask();
 195         if (taskReceived instanceof GetPredecessorAnswerTask) {
 196           predecessorId = ((GetPredecessorAnswerTask) taskReceived).getAnswerId();
 197           stop = true;
 198         } else {
 199           handleTask(taskReceived);
 200         }
 201         commReceive = null;
 202       } while (!stop);
 203     }
 204     catch (MsgException e) {
 205       Msg.debug("Failed to send the Get Predecessor request");
 206     }
 207     commReceive = null;
 208
 209     return predecessorId;
 210   }
 211
 212   /**
 213    * @brief Makes the current node find the successor node of an id.
 214    * @param node the current node
 215    * @param id the id to find
 216    * @return the id of the successor node, or -1 if the request failed
 217    */
 218   private int findSuccessor(int id) {
 219     if (isInInterval(id, this.id + 1, fingers[0])) {
 220       return fingers[0];
 221     }
 222
 223     int closest = this.closestPrecedingNode(id);
 224     return remoteFindSuccessor(closest, id);
 225   }
 226
 227   // Asks another node the successor node of an id.
 228   private int remoteFindSuccessor(int askTo, int id) {
 229     int successor = -1;
 230     boolean stop = false;
 231     String askToMailbox = Integer.toString(askTo);
 232     Task sendTask = new FindSuccessorTask(getHost().getName(), this.mailbox, id);
 233     Msg.debug("Sending a 'Find Successor' request to " + askToMailbox + " for id " + id);
 234     try {
 235       sendTask.send(askToMailbox, Common.TIMEOUT);
 236       do {
 237         if (commReceive == null) {
 238           commReceive = Task.irecv(this.mailbox);
 239         }
 240         commReceive.waitCompletion(Common.TIMEOUT);
 241         Task task = commReceive.getTask();
 242         if (task instanceof FindSuccessorAnswerTask) {
 243           //TODO: Check if this this our answer.
 244           FindSuccessorAnswerTask fTask = (FindSuccessorAnswerTask) task;
 245           stop = true;
 246           successor = fTask.getAnswerId();
 247         } else {
 248           handleTask(task);
 249         }
 250         commReceive = null;
 251       } while (!stop);
 252     }
 253     catch (TimeoutException e) {
 254       Msg.debug("Failed to send the 'Find Successor' request");
 255     }
 256     catch (MsgException e) {
 257       Msg.debug("Failed to receive Find Successor");
 258     }
 259     commReceive = null;
 260
 261     return successor;
 262   }
 263
 264   // This function is called periodically. It checks the immediate successor of the current node.
 265   private void stabilize() {
 266     Msg.debug("Stabilizing node");
 267     int candidateId;
 268     int successorId = fingers[0];
 269     if (successorId != this.id){
 270       candidateId = remoteGetPredecessor(successorId);
 271     } else {
 272       candidateId = predId;
 273     }
 274     //This node is a candidate to become my new successor
 275     if (candidateId != -1 && isInInterval(candidateId, this.id + 1, successorId - 1)) {
 276       setFinger(0, candidateId);
 277     }
 278     if (successorId != this.id) {
 279       remoteNotify(successorId, this.id);
 280     }
 281   }
 282
 283   /**
 284    * @brief Notifies the current node that its predecessor may have changed.
 285    * @param candidate_id the possible new predecessor
 286    */
 287   private void notify(int predecessorCandidateId) {
 288     if (predId == -1 || isInInterval(predecessorCandidateId, predId + 1, this.id - 1 )) {
 289       setPredecessor(predecessorCandidateId);
 290     }
 291   }
 292
 293   /**
 294    * @brief Notifies a remote node that its predecessor may have changed.
 295    * @param notify_id id of the node to notify
 296    * @param candidate_id the possible new predecessor
 297    */
 298   private void remoteNotify(int notifyId, int predecessorCandidateId) {
 299     Msg.debug("Sending a 'Notify' request to " + notifyId);
 300     Task sentTask = new NotifyTask(getHost().getName(), this.mailbox, predecessorCandidateId);
 301     sentTask.dsend(Integer.toString(notifyId));
 302   }
 303
 304   // This function is called periodically.
 305   // It refreshes the finger table of the current node.
 306   private void fixFingers() {
 307     Msg.debug("Fixing fingers");
 308     int successorId = findSuccessor(id + (1 << nextFingerToFix));
 309     if (successorId != -1) {
 310       if (successorId != fingers[nextFingerToFix]) {
 311         setFinger(nextFingerToFix, successorId);
 312       }
 313       nextFingerToFix = (nextFingerToFix + 1) % Common.NB_BITS;
 314     }
 315   }
 316
 317   // This function is called periodically.
 318   // It checks whether the predecessor has failed
 319   private void checkPredecessor() {
 320     //TODO
 321   }
 322
 323   // Performs a find successor request to a random id.
 324   private void randomLookup() {
 325     int dest = 1337;
 326     findSuccessor(dest);
 327   }
 328
 329   /**
 330    * @brief Returns the closest preceding finger of an id with respect to the finger table of the current node.
 331    * @param id the id to find
 332    * @return the closest preceding finger of that id
 333    */
 334   private int closestPrecedingNode(int id) {
 335     for (int i = Common.NB_BITS - 1; i >= 0; i--) {
 336       if (isInInterval(fingers[i], this.id + 1, id - 1)) {
 337         return fingers[i];
 338       }
 339     }
 340     return this.id;
 341   }
 342
 343   /**
 344    * @brief Returns whether an id belongs to the interval [start, end].
 345    *
 346    * The parameters are noramlized to make sure they are between 0 and nb_keys - 1).
 347    * 1 belongs to [62, 3]
 348    * 1 does not belong to [3, 62]
 349    * 63 belongs to [62, 3]
 350    * 63 does not belong to [3, 62]
 351    * 24 belongs to [21, 29]
 352    * 24 does not belong to [29, 21]
 353    *
 354    * @param id id to check
 355    * @param start lower bound
 356    * @param end upper bound
 357    * @return a non-zero value if id in in [start, end]
 358    */
 359   private static boolean isInInterval(int id, int start, int end) {
 360     int normId = normalize(id);
 361     int normStart = normalize(start);
 362     int normEnd = normalize(end);
 363
 364     // make sure end >= start and id >= start
 365     if (normEnd < normStart) {
 366       normEnd += Common.NB_KEYS;
 367     }
 368     if (normId < normStart) {
 369       normId += Common.NB_KEYS;
 370     }
 371     return (normId <= normEnd);
 372   }
 373
 374   /**
 375    * @brief Turns an id into an equivalent id in [0, nb_keys).
 376    * @param id an id
 377    * @return the corresponding normalized id
 378    */
 379   private static int normalize(int id) {
 380     return id & (Common.NB_KEYS - 1);
 381   }
 382
 383   /**
 384    * @brief Sets a finger of the current node.
 385    * @param finger_index index of the finger to set (0 to nb_bits - 1)
 386    * @param id the id to set for this finger
 387    */
 388   private void setFinger(int fingerIndex, int id) {
 389     if (id != fingers[fingerIndex]) {
 390       fingers[fingerIndex] = id;
 391       lastChangeDate = Msg.getClock();
 392     }
 393   }
 394 }