examples/s4u/dht-chord/s4u-dht-chord-node.cpp

   1 /* Copyright (c) 2010-2020. 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 #include "s4u-dht-chord.hpp"
   7
   8 XBT_LOG_EXTERNAL_DEFAULT_CATEGORY(s4u_chord);
   9
  10 /* Returns whether an id belongs to the interval [start, end].
  11  *
  12  * The parameters are normalized to make sure they are between 0 and nb_keys - 1).
  13  * 1 belongs to [62, 3]
  14  * 1 does not belong to [3, 62]
  15  * 63 belongs to [62, 3]
  16  * 63 does not belong to [3, 62]
  17  * 24 belongs to [21, 29]
  18  * 24 does not belong to [29, 21]
  19  *
  20  * @param id id to check
  21  * @param start lower bound
  22  * @param end upper bound
  23  * @return true if id in in [start, end]
  24  */
  25 static bool is_in_interval(int id, int start, int end)
  26 {
  27   int i = id % nb_keys;
  28   int s = start % nb_keys;
  29   int e = end % nb_keys;
  30
  31   // make sure end >= start and id >= start
  32   if (e < s) {
  33     e += nb_keys;
  34   }
  35
  36   if (i < s) {
  37     i += nb_keys;
  38   }
  39
  40   return i <= e;
  41 }
  42
  43 void ChordMessage::destroy(void* message)
  44 {
  45   delete static_cast<ChordMessage*>(message);
  46 }
  47
  48 /* Initializes the current node as the first one of the system */
  49 Node::Node(std::vector<std::string> args)
  50 {
  51   xbt_assert(args.size() == 3 || args.size() == 5, "Wrong number of arguments for this node");
  52
  53   // initialize my node
  54   id_                = std::stoi(args[1]);
  55   mailbox_           = simgrid::s4u::Mailbox::by_name(std::to_string(id_));
  56   next_finger_to_fix = 0;
  57   fingers_.resize(nb_bits, id_);
  58
  59   if (args.size() == 3) { // first ring
  60     deadline_   = std::stod(args[2]);
  61     start_time_ = simgrid::s4u::Engine::get_clock();
  62     XBT_DEBUG("Create a new Chord ring...");
  63   } else {
  64     known_id_   = std::stoi(args[2]);
  65     start_time_ = std::stod(args[3]);
  66     deadline_   = std::stod(args[4]);
  67     XBT_DEBUG("Hey! Let's join the system in %f seconds (shall leave at time %f)", start_time_,
  68               start_time_ + deadline_);
  69   }
  70 }
  71
  72 /* Makes the current node join the ring, knowing the id of a node already in the ring
  73  *
  74  * @param known_id id of a node already in the ring
  75  * @return true if the join operation succeeded
  76  *  */
  77
  78 void Node::join(int known_id)
  79 {
  80   XBT_INFO("Joining the ring with id %d, knowing node %d", id_, known_id);
  81   setPredecessor(-1); // no predecessor (yet)
  82
  83   int successor_id = remoteFindSuccessor(known_id, id_);
  84   if (successor_id == -1) {
  85     XBT_INFO("Cannot join the ring.");
  86   } else {
  87     setFinger(0, successor_id);
  88     printFingerTable();
  89     joined = true;
  90   }
  91 }
  92
  93 /* Makes the current node quit the system */
  94 void Node::leave()
  95 {
  96   XBT_INFO("Well Guys! I Think it's time for me to leave ;)");
  97   notifyAndQuit();
  98   joined = false;
  99 }
 100
 101 /* Notifies the successor and the predecessor of the current node before leaving */
 102 void Node::notifyAndQuit()
 103 {
 104   // send the PREDECESSOR_LEAVING to our successor
 105   ChordMessage* pred_msg = new ChordMessage(PREDECESSOR_LEAVING);
 106   pred_msg->request_id   = pred_id_;
 107   pred_msg->answer_to    = mailbox_;
 108
 109   XBT_DEBUG("Sending a 'PREDECESSOR_LEAVING' to my successor %d", fingers_[0]);
 110   try {
 111     simgrid::s4u::Mailbox::by_name(std::to_string(fingers_[0]))->put(pred_msg, 10, timeout);
 112   } catch (const simgrid::TimeoutException&) {
 113     XBT_DEBUG("Timeout expired when sending a 'PREDECESSOR_LEAVING' to my successor %d", fingers_[0]);
 114     delete pred_msg;
 115   }
 116
 117   if (pred_id_ != -1 && pred_id_ != id_) {
 118     // send the SUCCESSOR_LEAVING to our predecessor (only if I have one that is not me)
 119     ChordMessage* succ_msg = new ChordMessage(SUCCESSOR_LEAVING);
 120     succ_msg->request_id   = fingers_[0];
 121     succ_msg->answer_to    = mailbox_;
 122     XBT_DEBUG("Sending a 'SUCCESSOR_LEAVING' to my predecessor %d", pred_id_);
 123
 124     try {
 125       simgrid::s4u::Mailbox::by_name(std::to_string(pred_id_))->put(succ_msg, 10, timeout);
 126     } catch (const simgrid::TimeoutException&) {
 127       XBT_DEBUG("Timeout expired when sending a 'SUCCESSOR_LEAVING' to my predecessor %d", pred_id_);
 128       delete succ_msg;
 129     }
 130   }
 131 }
 132
 133 /* Performs a find successor request to a random id */
 134 void Node::randomLookup()
 135 {
 136   int res          = id_;
 137   int random_index = simgrid::xbt::random::uniform_int(0, nb_bits - 1);
 138   int random_id    = fingers_[random_index];
 139   XBT_DEBUG("Making a lookup request for id %d", random_id);
 140   if (random_id != id_)
 141     res = findSuccessor(random_id);
 142   XBT_DEBUG("The successor of node %d is %d", random_id, res);
 143 }
 144
 145 /* Sets a finger of the current node.
 146  *
 147  * @param node the current node
 148  * @param finger_index index of the finger to set (0 to nb_bits - 1)
 149  * @param id the id to set for this finger
 150  */
 151 void Node::setFinger(int finger_index, int id)
 152 {
 153   if (id != fingers_[finger_index]) {
 154     fingers_[finger_index] = id;
 155     XBT_VERB("My new finger #%d is %d", finger_index, id);
 156   }
 157 }
 158
 159 /* Sets the predecessor of the current node.
 160  * @param id the id to predecessor, or -1 to unset the predecessor
 161  */
 162 void Node::setPredecessor(int predecessor_id)
 163 {
 164   if (predecessor_id != pred_id_) {
 165     pred_id_ = predecessor_id;
 166     XBT_VERB("My new predecessor is %d", predecessor_id);
 167   }
 168 }
 169
 170 /** refreshes the finger table of the current node (called periodically) */
 171 void Node::fixFingers()
 172 {
 173   XBT_DEBUG("Fixing fingers");
 174   int id = findSuccessor(id_ + (1U << next_finger_to_fix));
 175   if (id != -1) {
 176     if (id != fingers_[next_finger_to_fix]) {
 177       setFinger(next_finger_to_fix, id);
 178       printFingerTable();
 179     }
 180     next_finger_to_fix = (next_finger_to_fix + 1) % nb_bits;
 181   }
 182 }
 183
 184 /** Displays the finger table of a node. */
 185 void Node::printFingerTable()
 186 {
 187   if (XBT_LOG_ISENABLED(s4u_chord, xbt_log_priority_verbose)) {
 188     XBT_VERB("My finger table:");
 189     XBT_VERB("Start | Succ");
 190     for (int i = 0; i < nb_bits; i++) {
 191       XBT_VERB(" %3u  | %3d", (id_ + (1U << i)) % nb_keys, fingers_[i]);
 192     }
 193
 194     XBT_VERB("Predecessor: %d", pred_id_);
 195   }
 196 }
 197
 198 /* checks whether the predecessor has failed (called periodically) */
 199 void Node::checkPredecessor()
 200 {
 201   XBT_DEBUG("Checking whether my predecessor is alive");
 202   void* data = nullptr;
 203   if (pred_id_ == -1)
 204     return;
 205
 206   simgrid::s4u::Mailbox* mailbox        = simgrid::s4u::Mailbox::by_name(std::to_string(pred_id_));
 207   simgrid::s4u::Mailbox* return_mailbox = simgrid::s4u::Mailbox::by_name(std::to_string(id_) + "_is_alive");
 208
 209   ChordMessage* message = new ChordMessage(PREDECESSOR_ALIVE);
 210   message->request_id   = pred_id_;
 211   message->answer_to    = return_mailbox;
 212
 213   XBT_DEBUG("Sending a 'Predecessor Alive' request to my predecessor %d", pred_id_);
 214   try {
 215     mailbox->put(message, 10, timeout);
 216   } catch (const simgrid::TimeoutException&) {
 217     XBT_DEBUG("Failed to send the 'Predecessor Alive' request to %d", pred_id_);
 218     delete message;
 219     return;
 220   }
 221
 222   // receive the answer
 223   XBT_DEBUG("Sent 'Predecessor Alive' request to %d, waiting for the answer on my mailbox '%s'", pred_id_,
 224             message->answer_to->get_cname());
 225   simgrid::s4u::CommPtr comm = return_mailbox->get_async(&data);
 226
 227   try {
 228     comm->wait_for(timeout);
 229     XBT_DEBUG("Received the answer to my 'Predecessor Alive': my predecessor %d is alive", pred_id_);
 230     delete static_cast<ChordMessage*>(data);
 231   } catch (const simgrid::TimeoutException&) {
 232     XBT_DEBUG("Failed to receive the answer to my 'Predecessor Alive' request");
 233     pred_id_ = -1;
 234   }
 235 }
 236
 237 /* Asks its predecessor to a remote node
 238  *
 239  * @param ask_to the node to ask to
 240  * @return the id of its predecessor node, or -1 if the request failed (or if the node does not know its predecessor)
 241  */
 242 int Node::remoteGetPredecessor(int ask_to)
 243 {
 244   int predecessor_id                      = -1;
 245   void* data                              = nullptr;
 246   simgrid::s4u::Mailbox* mailbox          = simgrid::s4u::Mailbox::by_name(std::to_string(ask_to));
 247   simgrid::s4u::Mailbox* return_mailbox   = simgrid::s4u::Mailbox::by_name(std::to_string(id_) + "_pred");
 248
 249   ChordMessage* message = new ChordMessage(GET_PREDECESSOR);
 250   message->request_id   = id_;
 251   message->answer_to    = return_mailbox;
 252
 253   // send a "Get Predecessor" request to ask_to_id
 254   XBT_DEBUG("Sending a 'Get Predecessor' request to %d", ask_to);
 255   try {
 256     mailbox->put(message, 10, timeout);
 257   } catch (const simgrid::TimeoutException&) {
 258     XBT_DEBUG("Failed to send the 'Get Predecessor' request to %d", ask_to);
 259     delete message;
 260     return predecessor_id;
 261   }
 262
 263   // receive the answer
 264   XBT_DEBUG("Sent 'Get Predecessor' request to %d, waiting for the answer on my mailbox '%s'", ask_to,
 265             message->answer_to->get_cname());
 266   simgrid::s4u::CommPtr comm = return_mailbox->get_async(&data);
 267
 268   try {
 269     comm->wait_for(timeout);
 270     const ChordMessage* answer = static_cast<ChordMessage*>(data);
 271     XBT_DEBUG("Received the answer to my 'Get Predecessor' request: the predecessor of node %d is %d", ask_to,
 272               answer->answer_id);
 273     predecessor_id = answer->answer_id;
 274     delete answer;
 275   } catch (const simgrid::TimeoutException&) {
 276     XBT_DEBUG("Failed to receive the answer to my 'Get Predecessor' request");
 277     delete static_cast<ChordMessage*>(data);
 278   }
 279
 280   return predecessor_id;
 281 }
 282
 283 /* Returns the closest preceding finger of an id with respect to the finger table of the current node.
 284  *
 285  * @param id the id to find
 286  * @return the closest preceding finger of that id
 287  */
 288 int Node::closestPrecedingFinger(int id)
 289 {
 290   for (int i = nb_bits - 1; i >= 0; i--) {
 291     if (is_in_interval(fingers_[i], id_ + 1, id - 1)) {
 292       return fingers_[i];
 293     }
 294   }
 295   return id_;
 296 }
 297
 298 /* Makes the current node find the successor node of an id.
 299  *
 300  * @param id the id to find
 301  * @return the id of the successor node, or -1 if the request failed
 302  */
 303 int Node::findSuccessor(int id)
 304 {
 305   // is my successor the successor?
 306   if (is_in_interval(id, id_ + 1, fingers_[0])) {
 307     return fingers_[0];
 308   }
 309
 310   // otherwise, ask the closest preceding finger in my table
 311   return remoteFindSuccessor(closestPrecedingFinger(id), id);
 312 }
 313
 314 int Node::remoteFindSuccessor(int ask_to, int id)
 315 {
 316   int successor                           = -1;
 317   void* data                              = nullptr;
 318   simgrid::s4u::Mailbox* mailbox          = simgrid::s4u::Mailbox::by_name(std::to_string(ask_to));
 319   simgrid::s4u::Mailbox* return_mailbox   = simgrid::s4u::Mailbox::by_name(std::to_string(id_) + "_succ");
 320
 321   ChordMessage* message = new ChordMessage(FIND_SUCCESSOR);
 322   message->request_id   = id_;
 323   message->answer_to    = return_mailbox;
 324
 325   // send a "Find Successor" request to ask_to_id
 326   XBT_DEBUG("Sending a 'Find Successor' request to %d for id %d", ask_to, id);
 327   try {
 328     mailbox->put(message, 10, timeout);
 329   } catch (const simgrid::TimeoutException&) {
 330     XBT_DEBUG("Failed to send the 'Find Successor' request to %d for id %d", ask_to, id_);
 331     delete message;
 332     return successor;
 333   }
 334   // receive the answer
 335   XBT_DEBUG("Sent a 'Find Successor' request to %d for key %d, waiting for the answer", ask_to, id);
 336   simgrid::s4u::CommPtr comm = return_mailbox->get_async(&data);
 337
 338   try {
 339     comm->wait_for(timeout);
 340     const ChordMessage* answer = static_cast<ChordMessage*>(data);
 341     XBT_DEBUG("Received the answer to my 'Find Successor' request for id %d: the successor of key %d is %d",
 342               answer->request_id, id_, answer->answer_id);
 343     successor = answer->answer_id;
 344     delete answer;
 345   } catch (const simgrid::TimeoutException&) {
 346     XBT_DEBUG("Failed to receive the answer to my 'Find Successor' request");
 347     delete static_cast<ChordMessage*>(data);
 348   }
 349
 350   return successor;
 351 }
 352
 353 /* Notifies the current node that its predecessor may have changed. */
 354 void Node::notify(int predecessor_candidate_id)
 355 {
 356   if (pred_id_ == -1 || is_in_interval(predecessor_candidate_id, pred_id_ + 1, id_ - 1)) {
 357     setPredecessor(predecessor_candidate_id);
 358     printFingerTable();
 359   } else {
 360     XBT_DEBUG("I don't have to change my predecessor to %d", predecessor_candidate_id);
 361   }
 362 }
 363
 364 /* Notifies a remote node that its predecessor may have changed. */
 365 void Node::remoteNotify(int notify_id, int predecessor_candidate_id)
 366 {
 367   ChordMessage* message = new ChordMessage(NOTIFY);
 368   message->request_id   = predecessor_candidate_id;
 369   message->answer_to    = nullptr;
 370
 371   // send a "Notify" request to notify_id
 372   XBT_DEBUG("Sending a 'Notify' request to %d", notify_id);
 373   simgrid::s4u::Mailbox* mailbox = simgrid::s4u::Mailbox::by_name(std::to_string(notify_id));
 374   mailbox->put_init(message, 10)->detach(ChordMessage::destroy);
 375 }
 376
 377 /* This function is called periodically. It checks the immediate successor of the current node. */
 378 void Node::stabilize()
 379 {
 380   XBT_DEBUG("Stabilizing node");
 381
 382   // get the predecessor of my immediate successor
 383   int candidate_id = pred_id_;
 384   int successor_id = fingers_[0];
 385   if (successor_id != id_)
 386     candidate_id = remoteGetPredecessor(successor_id);
 387
 388   // this node is a candidate to become my new successor
 389   if (candidate_id != -1 && is_in_interval(candidate_id, id_ + 1, successor_id - 1)) {
 390     setFinger(0, candidate_id);
 391   }
 392   if (successor_id != id_) {
 393     remoteNotify(successor_id, id_);
 394   }
 395 }
 396
 397 /* This function is called when a node receives a message.
 398  *
 399  * @param message the message to handle (don't touch it afterward: it will be destroyed, reused or forwarded)
 400  */
 401 void Node::handleMessage(ChordMessage* message)
 402 {
 403   switch (message->type) {
 404   case FIND_SUCCESSOR:
 405     XBT_DEBUG("Received a 'Find Successor' request from %s for id %d", message->issuer_host_name.c_str(),
 406         message->request_id);
 407     // is my successor the successor?
 408     if (is_in_interval(message->request_id, id_ + 1, fingers_[0])) {
 409       message->type = FIND_SUCCESSOR_ANSWER;
 410       message->answer_id = fingers_[0];
 411       XBT_DEBUG("Sending back a 'Find Successor Answer' to %s (mailbox %s): the successor of %d is %d",
 412                 message->issuer_host_name.c_str(), message->answer_to->get_cname(), message->request_id,
 413                 message->answer_id);
 414       message->answer_to->put_init(message, 10)->detach(ChordMessage::destroy);
 415     } else {
 416       // otherwise, forward the request to the closest preceding finger in my table
 417       int closest = closestPrecedingFinger(message->request_id);
 418       XBT_DEBUG("Forwarding the 'Find Successor' request for id %d to my closest preceding finger %d",
 419           message->request_id, closest);
 420       simgrid::s4u::Mailbox* mailbox = simgrid::s4u::Mailbox::by_name(std::to_string(closest));
 421       mailbox->put_init(message, 10)->detach(ChordMessage::destroy);
 422     }
 423     break;
 424
 425   case GET_PREDECESSOR:
 426     XBT_DEBUG("Receiving a 'Get Predecessor' request from %s", message->issuer_host_name.c_str());
 427     message->type = GET_PREDECESSOR_ANSWER;
 428     message->answer_id = pred_id_;
 429     XBT_DEBUG("Sending back a 'Get Predecessor Answer' to %s via mailbox '%s': my predecessor is %d",
 430               message->issuer_host_name.c_str(), message->answer_to->get_cname(), message->answer_id);
 431     message->answer_to->put_init(message, 10)->detach(ChordMessage::destroy);
 432     break;
 433
 434   case NOTIFY:
 435     // someone is telling me that he may be my new predecessor
 436     XBT_DEBUG("Receiving a 'Notify' request from %s", message->issuer_host_name.c_str());
 437     notify(message->request_id);
 438     delete message;
 439     break;
 440
 441   case PREDECESSOR_LEAVING:
 442     // my predecessor is about to quit
 443     XBT_DEBUG("Receiving a 'Predecessor Leaving' message from %s", message->issuer_host_name.c_str());
 444     // modify my predecessor
 445     setPredecessor(message->request_id);
 446     delete message;
 447     /*TODO :
 448       >> notify my new predecessor
 449       >> send a notify_predecessors !!
 450      */
 451     break;
 452
 453   case SUCCESSOR_LEAVING:
 454     // my successor is about to quit
 455     XBT_DEBUG("Receiving a 'Successor Leaving' message from %s", message->issuer_host_name.c_str());
 456     // modify my successor FIXME : this should be implicit ?
 457     setFinger(0, message->request_id);
 458     delete message;
 459     /* TODO
 460        >> notify my new successor
 461        >> update my table & predecessors table */
 462     break;
 463
 464   case PREDECESSOR_ALIVE:
 465     XBT_DEBUG("Receiving a 'Predecessor Alive' request from %s", message->issuer_host_name.c_str());
 466     message->type = PREDECESSOR_ALIVE_ANSWER;
 467     XBT_DEBUG("Sending back a 'Predecessor Alive Answer' to %s (mailbox %s)", message->issuer_host_name.c_str(),
 468               message->answer_to->get_cname());
 469     message->answer_to->put_init(message, 10)->detach(ChordMessage::destroy);
 470     break;
 471
 472   default:
 473     XBT_DEBUG("Ignoring unexpected message: %d from %s", message->type, message->issuer_host_name.c_str());
 474     delete message;
 475   }
 476 }