Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
a9a9511af2564c8df5deb0d997a217324cc43f01
[simgrid.git] / 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       try {
190         do {
191           if (commReceive == null) {
192             commReceive = Task.irecv(this.mailbox);
193           }
194           commReceive.waitCompletion(Common.TIMEOUT);
195           Task taskReceived = commReceive.getTask();
196           if (taskReceived instanceof GetPredecessorAnswerTask) {
197             predecessorId = ((GetPredecessorAnswerTask) taskReceived).getAnswerId();
198             stop = true;
199           } else {
200             handleTask(taskReceived);
201           }
202           commReceive = null;
203         } while (!stop);
204       }
205       catch (MsgException e) {
206         commReceive = null;
207       }
208     }
209     catch (MsgException e) {
210       Msg.debug("Failed to send the Get Predecessor request");
211     }
212     return predecessorId;
213   }
214
215   /**
216    * @brief Makes the current node find the successor node of an id.
217    * @param node the current node
218    * @param id the id to find
219    * @return the id of the successor node, or -1 if the request failed
220    */
221   private int findSuccessor(int id) {
222     if (isInInterval(id, this.id + 1, fingers[0])) {
223       return fingers[0];
224     }
225
226     int closest = this.closestPrecedingNode(id);
227     return remoteFindSuccessor(closest, id);
228   }
229
230   // Asks another node the successor node of an id.
231   private int remoteFindSuccessor(int askTo, int id) {
232     int successor = -1;
233     boolean stop = false;
234     String askToMailbox = Integer.toString(askTo);
235     Task sendTask = new FindSuccessorTask(getHost().getName(), this.mailbox, id);
236     Msg.debug("Sending a 'Find Successor' request to " + askToMailbox + " for id " + id);
237     try {
238       sendTask.send(askToMailbox, Common.TIMEOUT);
239       do {
240         if (commReceive == null) {
241           commReceive = Task.irecv(this.mailbox);
242         }
243         try {
244           commReceive.waitCompletion(Common.TIMEOUT);
245           Task task = commReceive.getTask();
246           if (task instanceof FindSuccessorAnswerTask) {
247             //TODO: Check if this this our answer.
248             FindSuccessorAnswerTask fTask = (FindSuccessorAnswerTask) task;
249             stop = true;
250             successor = fTask.getAnswerId();
251           } else {
252             handleTask(task);
253           }
254           commReceive = null;
255         }
256         catch (TimeoutException e) {
257           stop = true;
258           commReceive = null;
259         }
260       } while (!stop);
261     }
262     catch (TimeoutException e) {
263       Msg.debug("Failed to send the 'Find Successor' request");
264     }
265     catch (MsgException e) {
266       Msg.debug("Failed to receive Find Successor");
267     }
268
269     return successor;
270   }
271
272   // This function is called periodically. It checks the immediate successor of the current node.
273   private void stabilize() {
274     Msg.debug("Stabilizing node");
275     int candidateId;
276     int successorId = fingers[0];
277     if (successorId != this.id){
278       candidateId = remoteGetPredecessor(successorId);
279     } else {
280       candidateId = predId;
281     }
282     //This node is a candidate to become my new successor
283     if (candidateId != -1 && isInInterval(candidateId, this.id + 1, successorId - 1)) {
284       setFinger(0, candidateId);
285     }
286     if (successorId != this.id) {
287       remoteNotify(successorId, this.id);
288     }
289   }
290
291   /**
292    * @brief Notifies the current node that its predecessor may have changed.
293    * @param candidate_id the possible new predecessor
294    */
295   private void notify(int predecessorCandidateId) {
296     if (predId == -1 || isInInterval(predecessorCandidateId, predId + 1, this.id - 1 )) {
297       setPredecessor(predecessorCandidateId);
298     }
299   }
300
301   /**
302    * @brief Notifies a remote node that its predecessor may have changed.
303    * @param notify_id id of the node to notify
304    * @param candidate_id the possible new predecessor
305    */
306   private void remoteNotify(int notifyId, int predecessorCandidateId) {
307     Msg.debug("Sending a 'Notify' request to " + notifyId);
308     Task sentTask = new NotifyTask(getHost().getName(), this.mailbox, predecessorCandidateId);
309     sentTask.dsend(Integer.toString(notifyId));
310   }
311
312   // This function is called periodically.
313   // It refreshes the finger table of the current node.
314   private void fixFingers() {
315     Msg.debug("Fixing fingers");
316     int i = this.nextFingerToFix;
317     int successorId = this.findSuccessor(this.id + (int)Math.pow(2,i)); //FIXME: SLOW
318     if (successorId != -1) {
319       if (successorId != fingers[i]) {
320         setFinger(i, successorId);
321       }
322       nextFingerToFix = (i + 1) % Common.NB_BITS;
323     }
324   }
325
326   // This function is called periodically.
327   // It checks whether the predecessor has failed
328   private void checkPredecessor() {
329     //TODO
330   }
331
332   // Performs a find successor request to a random id.
333   private void randomLookup() {
334     int dest = 1337;
335     findSuccessor(dest);
336   }
337
338   /**
339    * @brief Returns the closest preceding finger of an id with respect to the finger table of the current node.
340    * @param id the id to find
341    * @return the closest preceding finger of that id
342    */
343   private int closestPrecedingNode(int id) {
344     for (int i = Common.NB_BITS - 1; i >= 0; i--) {
345       if (isInInterval(fingers[i], this.id + 1, id - 1)) {
346         return fingers[i];
347       }
348     }
349     return this.id;
350   }
351
352   /**
353    * @brief Returns whether an id belongs to the interval [start, end].
354    *
355    * The parameters are noramlized to make sure they are between 0 and nb_keys - 1).
356    * 1 belongs to [62, 3]
357    * 1 does not belong to [3, 62]
358    * 63 belongs to [62, 3]
359    * 63 does not belong to [3, 62]
360    * 24 belongs to [21, 29]
361    * 24 does not belong to [29, 21]
362    *
363    * @param id id to check
364    * @param start lower bound
365    * @param end upper bound
366    * @return a non-zero value if id in in [start, end]
367    */
368   private static boolean isInInterval(int id, int start, int end) {
369     int normId = normalize(id);
370     int normStart = normalize(start);
371     int normEnd = normalize(end);
372
373     // make sure end >= start and id >= start
374     if (normEnd < normStart) {
375       normEnd += Common.NB_KEYS;
376     }
377     if (normId < normStart) {
378       normId += Common.NB_KEYS;
379     }
380     return (normId <= normEnd);
381   }
382
383   /**
384    * @brief Turns an id into an equivalent id in [0, nb_keys).
385    * @param id an id
386    * @return the corresponding normalized id
387    */
388   private static int normalize(int id) {
389     return id & (Common.NB_KEYS - 1);
390   }
391
392   /**
393    * @brief Sets a finger of the current node.
394    * @param finger_index index of the finger to set (0 to nb_bits - 1)
395    * @param id the id to set for this finger
396    */
397   private void setFinger(int fingerIndex, int id) {
398     if (id != fingers[fingerIndex]) {
399       fingers[fingerIndex] = id;
400       lastChangeDate = Msg.getClock();
401     }
402   }
403 }