examples/lua/chord/chord.lua

   1 -- A SimGrid Lua implementation of the Chord DHT
   2
   3 -- Copyright (c) 2011-2012, 2014. The SimGrid Team.
   4 -- All rights reserved.
   5
   6 -- This program is free software; you can redistribute it and/or modify it
   7 -- under the terms of the license (GNU LGPL) which comes with this package.
   8
   9 require("simgrid")
  10
  11 nb_bits                 = 24
  12 nb_keys                 = 2^nb_bits
  13 comp_size               = 0
  14 comm_size               = 10
  15 timeout                 = 50
  16 max_simulation_time     = 1000
  17 stabilize_delay         = 20
  18 fix_fingers_delay       = 120
  19 check_predecessor_delay = 120
  20 lookup_delay            = 10
  21
  22 -- current node (don't worry, globals are duplicated in each simulated process)
  23 my_node = {
  24   -- FIXME: my_id does not exist.
  25   id = my_id,
  26   next_finger_to_fix = 1,
  27   fingers = {},
  28   predecessor = nil,
  29   comm_recv = nil
  30 }
  31
  32 -- Main function of each Chord process
  33 -- Arguments:
  34 -- - my id
  35 -- - the id of a guy I know in the system (except for the first node)
  36 function node(...)
  37
  38   simgrid.info("Hi! This is my first message; I just entered the program!")
  39   -- TODO simplify the deployment file
  40   local known_id
  41   local args = {...}
  42   my_node.id = math.tointeger(args[1])
  43   simgrid.info("My id is now " .. my_node.id)
  44   if #args == 4 then
  45     known_id = math.tointeger(args[2])
  46     simgrid.info("Updated my known_id to " .. known_id)
  47   end
  48
  49   -- initialize the node and the fingertable;
  50   -- at the beginning, this node only knows itself (we need to discover others)
  51   for i = 1, nb_bits, 1 do
  52     my_node.fingers[i] = my_node.id
  53   end
  54
  55   -- Let's make sure we can receive messages!
  56   my_node.comm_recv = simgrid.task.irecv(my_node.id)
  57
  58   -- join the ring
  59   local join_success = false
  60   --simgrid.info(known_id)
  61
  62   if known_id == nil then
  63     -- only the first node ("Jacqueline") will enter here
  64     -- as configured in file ../../msg/chord/chord.xml
  65     simgrid.info("First node here. Going to create everything.")
  66     create()
  67     join_success = true
  68   else
  69     -- Communicate to the first node and join the ring there
  70     -- This will also initialize
  71     -- my_node.predecessor and my_node.successor
  72     join_success = join(known_id)
  73   end
  74
  75   -- At this point, finger[1] does not necessarily actually point
  76   -- to the *real* successor; it might be that the first node still
  77   -- didn't notify us that another node joined with
  78   -- an ID that satisfies my_id <= ID <= current_successorId
  79
  80   -- TODO Remove this, but make sure my_node.predecessor is initialized somewhere
  81   --if my_node.id == 1 then
  82       --simgrid.info("YUHU!")
  83       --my_node.predecessor = 1
  84   --end
  85
  86   -- main loop
  87   if join_success then
  88
  89     local now                         = simgrid.get_clock()
  90     local next_stabilize_date         = now + stabilize_delay
  91     local next_fix_fingers_date       = now + fix_fingers_delay
  92     local next_check_predecessor_date = now + check_predecessor_delay
  93     local next_lookup_date            = now + lookup_delay
  94
  95     local task, err
  96
  97     simgrid.debug("I'm now entering the main loop.")
  98
  99     while now < max_simulation_time do
 100
 101       task, err = my_node.comm_recv:test()
 102       simgrid.info(now .. " " .. next_stabilize_date .. " " .. now + stabilize_delay .. " " .. next_fix_fingers_date .. " " .. next_check_predecessor_date .. " " .. next_lookup_date)
 103
 104       if task then
 105         -- I received a task: answer it
 106         simgrid.info("I received a task of type '" .. task.type .."'! My id is " .. my_node.id)
 107         my_node.comm_recv = simgrid.task.irecv(my_node.id)
 108         handle_task(task)
 109       elseif err then
 110         -- the communication has failed: nevermind, we'll try again
 111         simgrid.info("Error while receiving a task! My id is " .. my_node.id)
 112         my_node.comm_recv = simgrid.task.irecv(my_node.id)
 113       else
 114         -- no task was received: do periodic calls
 115
 116         if now >= next_stabilize_date then
 117           simgrid.debug("Stabilizing...")
 118           stabilize()
 119           simgrid.debug("Finished stabilizing!")
 120           next_stabilize_date = simgrid.get_clock() + stabilize_delay
 121
 122         --elseif now >= next_fix_fingers_date then
 123           --fix_fingers()
 124           --next_fix_fingers_date = simgrid.get_clock() + fix_fingers_delay
 125
 126         --elseif now >= next_check_predecessor_date then
 127           --check_predecessor()
 128           --next_check_predecessor_date = simgrid.get_clock() + check_predecessor_delay
 129
 130         --elseif now >= next_lookup_date then
 131           --random_lookup()
 132           --simgrid.debug("I'm now executing a lookup, as lookup_delay makes me do this. " .. simgrid.get_clock())
 133           --next_lookup_date = simgrid.get_clock() + lookup_delay
 134
 135         else
 136           ---- nothing to do: sleep for a while
 137           --simgrid.debug("Didn't have to stabilize, update my fingers, check my predecessors or do a random lookup; hence, I'm starting to sleep now...")
 138           simgrid.process.sleep(5)
 139           --simgrid.debug("Slept for 5s")
 140         end
 141       end
 142       now = simgrid.get_clock()
 143     end -- while
 144
 145     -- leave the ring
 146     leave()
 147   end
 148 end
 149
 150 -- Makes the current node leave the ring
 151 function leave()
 152
 153   simgrid.info("Leaving the ring, because max_simulation_time was reached.")
 154   -- TODO: notify others
 155 end
 156
 157 -- This function is called when the current node receives a task
 158 -- and can not immediately deal with it; for instance, if the host
 159 -- waits on a response for a 'find successor' query but receives a
 160 -- 'get predecessor' message instead; we cannot just discard this
 161 -- message so we deal with it here.
 162 --
 163 -- - task: the task received
 164 function handle_task(task)
 165
 166   simgrid.debug("Handling task in handle_task()")
 167   local type = task.type
 168
 169   if type == "find successor" then
 170
 171     task.answer_to = math.tointeger(task.answer_to)
 172     task.request_id = math.tointeger(task.request_id)
 173
 174     simgrid.info("Received a 'find successor' request from " .. string.format("%d", task.answer_to) ..
 175         " for id " .. string.format("%d", task.request_id))
 176
 177     -- Is my successor have the right host? This can happen if there are holes
 178     -- in the ring; for instance, if my id is 13 and my successor is 17 and
 179     -- 14,15,16 don't exist but I'm asked for 15, then yes, 17 is the right
 180     -- answer to the request.
 181     --
 182     -- Test: my_node.id + 1 <= task.request_id <= my_node.fingers[1]
 183     --                  ^^^
 184     -- TODO: Why the +1? We could receive this message from a host that forwarded
 185     --       this message (and the original sender doesn't know us),
 186     --       so why do we exclude ourselves?
 187     if is_in_interval(task.request_id, my_node.id + 1, my_node.fingers[1]) then
 188
 189       simgrid.info("Sending back a 'find successor answer' to " ..
 190           string.format("%d", task.answer_to) .. ": the successor of " .. string.format("%d", task.request_id) ..
 191           " is " .. string.format("%d", my_node.fingers[1]))
 192
 193       task.type = "find successor answer"
 194       -- TODO: Can we remove the "" here?
 195       task.answer = math.tointeger(my_node.fingers[1])
 196       simgrid.info("Answer" .. task.answer)
 197       task:dsend(math.tointeger(task.answer_to))
 198     else
 199       -- forward the request to the closest preceding finger in my table
 200
 201       simgrid.info("Forwarding the 'find successor' request to my closest preceding finger")
 202       task:dsend(closest_preceding_node(task.request_id))
 203     end
 204
 205   elseif type == "get predecessor" then
 206     simgrid.info("Received a 'find predecessor' request from " .. string.format("%d", task.answer_to) ..
 207         " for id. Sending back an answer.")
 208
 209     task.type = "get predecessor answer"
 210
 211     --for i,v in pairs(my_node) do
 212         --print(my_node.id, i, v)
 213     --end
 214     --print(my_node.predecessor)
 215     if my_node.predecessor ~= nil then
 216       task.answer = math.tointeger(my_node.predecessor)
 217       --print(my_node.predecessor)
 218     else
 219       -- FIXME: This is completely wrong here. Fix this;
 220       --        we need to figure out what to send if we don't know our
 221       --        predecessor yet
 222       simgrid.critical("Don't know my predecessor yet!")
 223       my_node.predecessor = remote_get_predecessor(my_node.fingers[1])
 224       task.answer = my_node.predecessor
 225     end
 226
 227     --print("It will break now, since task.answer is nil here.")
 228     --task.answer = my_node.predecessor
 229     --print(task.answer)
 230     --print("Before")
 231     task:dsend(math.tointeger(task.answer_to))
 232     --print("After dsend returned")
 233
 234   elseif type == "notify" then
 235     -- someone is telling me that he may be my new predecessor
 236     simgrid.info("Host id " .. task.request_id .. " wants to be my predecessor")
 237     notify(math.tointeger(task.request_id))
 238
 239   elseif type == "predecessor leaving" then
 240     -- TODO
 241     simgrid.debug("predecessor leaving")
 242
 243   elseif type == "successor_leaving" then
 244     -- TODO: We could / should use something like table.remove(my_node.fingers, 1) here
 245     simgrid.debug(type)
 246
 247   elseif type == "find successor answer" then
 248     -- ignoring, this is handled in remote_find_successor
 249     simgrid.debug(type)
 250
 251   elseif type == "get predecessor answer" then
 252     -- ignoring, this is already handled in
 253
 254   else
 255     error("Unknown type of task received: " .. task.type)
 256   end
 257
 258   simgrid.info("I'm leaving handle_task() now.")
 259 end
 260
 261 -- Returns whether an id belongs to the interval [a, b[.
 262 -- The parameters are normalized to make sure they are between 0 and nb_keys - 1.
 263 -- 1 belongs to [62, 3].
 264 -- 1 does not belong to [3, 62].
 265 -- 63 belongs to [62, 3].
 266 -- 63 does not belong to [3, 62].
 267 -- 24 belongs to [21, 29].
 268 -- 24 does not belong to [29, 21].
 269 function is_in_interval(id, a, b)
 270   id= math.tointeger(id)
 271   a = math.tointeger(a)
 272   b = math.tointeger(b)
 273
 274   -- normalize the parameters
 275   -- TODO: Currently, nb_bits = 24; so a,b,id < 24! Really?
 276   id = id % nb_bits
 277   a = a % nb_bits
 278   b = b % nb_bits
 279
 280   -- make sure a <= b and a <= id
 281   if b < a then
 282     b = b + nb_keys
 283   end
 284
 285   if id < a then
 286     id = id + nb_keys
 287   end
 288
 289   return id <= b
 290 end
 291
 292 -- Returns whether the current node is in the ring.
 293 function has_joined()
 294
 295   return my_node.fingers[my_node.id] ~= nil
 296 end
 297
 298 -- Creates a new Chord ring.
 299 function create()
 300   simgrid.debug("I've now initialized my predecessor and fingertable.")
 301   --my_node.predecessor = my_node.id
 302   my_node.predecessor = nil
 303   my_node.fingers[1]  = my_node.id
 304 end
 305
 306 -- Attemps to join the Chord ring.
 307 -- - known_id: id of a node already in the ring
 308 -- - return value: true if the join was successful
 309 function join(known_id)
 310
 311   simgrid.info("Joining the ring with id " .. my_node.id .. ", knowing node " .. known_id)
 312
 313   local successor = remote_find_successor(known_id, my_node.id)
 314   simgrid.info("Returned from remote_find_successor; my successor is " .. successor)
 315   if successor == nil then
 316     simgrid.critical("Cannot join the ring.")
 317     return false
 318   end
 319
 320   -- We don't know the predecessor yet, so we initialize it with NULL
 321   my_node.predecessor = nil
 322   my_node.fingers[1] = successor
 323
 324   -- Everything was successfull!
 325   return true
 326 end
 327
 328 -- Returns the closest preceding finger of an id with respect to the finger
 329 -- table of the current node.
 330 -- - id: the id to find
 331 -- - return value: the closest preceding finger of that id
 332 function closest_preceding_node(id)
 333
 334   for i = nb_bits, 1, -1 do
 335     if is_in_interval(my_node.fingers[i], my_node.id + 1, id - 1) then
 336       -- finger i is the first one before id
 337       simgrid.info("fix_fingers: The closest preceding node for " .. id .. " is finger " .. i .. " (node " .. my_node.fingers[i] .. ")")
 338       return my_node.fingers[i]
 339     end
 340   end
 341 end
 342
 343 -- Finds the successor of an id
 344 -- id: the id to find
 345 -- return value: the id of the successor, or nil if the request failed
 346 function find_successor(id)
 347
 348   if is_in_interval(id, my_node.id + 1, my_node.fingers[1]) then
 349     -- my successor is the successor
 350     simgrid.info("Looking for successor of " .. id .. ", but I determined it's my own successor: " .. my_node.fingers[1])
 351     return my_node.fingers[1]
 352   else
 353     -- ask to the closest preceding finger in my table
 354     simgrid.info("fix_fingers: Looking for successor of " .. id .. ", checking closest preceding node")
 355     local ask_to = closest_preceding_node(id)
 356     simgrid.info("fix_fingers: Looking for successor of " .. id .. ", checking closest preceding node")
 357     return remote_find_successor(ask_to, id)
 358   end
 359
 360 end
 361
 362 -- Asks a remote node the successor of an id.
 363 -- ask_to: id of a remote node to ask to
 364 -- id: the id to find
 365 -- return value: the id of the successor, or nil if the request failed
 366 function remote_find_successor(ask_to, id)
 367
 368   local task      = simgrid.task.new("", comp_size, comm_size)
 369   task.type       = "find successor"
 370   task.request_id = id               -- This is the id we want to find
 371   task.answer_to  = my_node.id       -- This is where the answer needs to go
 372                                      -- (back to us)
 373
 374   simgrid.info("Sending a 'find successor' request to " .. ask_to .. " for id " .. id .. " (timeout=".. timeout .. ")")
 375   if task:send(ask_to, timeout) then
 376     -- request successfully sent: wait for an answer
 377
 378     while true do
 379       simgrid.info("New iteration in while loop of remote_find_successor(); I'm still waiting for a response!")
 380       --print(task.request_id)
 381       simgrid.info("Starting to wait for a message; timeout=" .. timeout)
 382       task = my_node.comm_recv:wait(timeout)
 383       simgrid.info("Finished to wait")
 384       -- TODO Do we need this?
 385       --for i,v in pairs(task) do
 386           --print(i, v)
 387       --end
 388       --simgrid.info("I will crash!")
 389       --task.answer = math.tointeger(task.answer)
 390       --simgrid.info("Ich denke task.type ist leer")
 391       --simgrid.info("Before irecv: " .. my_node.id)
 392
 393       -- Even if the recv above failed (timeout occurred) -- we want to be
 394       -- able to receive a message if it comes in, even without us explicitly
 395       -- calling the recv() method.
 396       my_node.comm_recv = simgrid.task.irecv(my_node.id)
 397
 398       if not task then
 399         -- failed to receive the answer
 400         return nil
 401       else
 402         -- a task was received: is it the expected answer (i.e., the response to
 403         -- our query and for the id we're interested in)
 404         if task.type ~= "find successor answer" or task.request_id ~= id then
 405           -- this is not our answer, but we still need to handle it.
 406           simgrid.info("Wrong request of type " .. task.type .. " received, expected 'find successor answer'")
 407           handle_task(task)
 408
 409         else
 410           -- this is our answer
 411           simgrid.info("Received the answer to my 'find successor' request for id " ..
 412           id .. ": the successor is " .. task.answer)
 413
 414           -- TODO: Do we need math.tointeger here?
 415           return math.tointeger(task.answer)
 416         end
 417       end
 418     end
 419   else
 420     simgrid.info("Failed to send the 'find successor' request to " .. ask_to ..
 421       " for id " .. id)
 422   end
 423
 424   -- This can never be reached, because if this host finds the successor, it
 425   -- will return it right away!
 426   simgrid.info("Whooops! I should never reach this statement, because I didn't find a successor!")
 427
 428   -- We need to return the successor here
 429 end
 430
 431 -- Asks a remote node its predecessor.
 432 -- ask_to: id of a remote node to ask to
 433 -- return value: the id of its predecessor, or nil if the request failed
 434 function remote_get_predecessor(ask_to)
 435
 436   local task = simgrid.task.new("", comp_size, comm_size)
 437   task.type = "get predecessor"
 438   task.answer_to = math.tointeger(my_node.id)
 439   -- TODO c.heinrich: Remove this
 440   --task.note = "Bla " .. ask_to .. " at time  " .. simgrid.get_clock()
 441
 442   simgrid.info("Sending request for '" .. task.type .."' to id '" .. ask_to .. "'")
 443   if task:send(ask_to, timeout) then
 444     simgrid.info("Done sending the request to " .. ask_to)
 445     -- request successfully sent: wait for an answer
 446     -- We need to iterate here because we might receive other
 447     -- messages too (but not the answer to the request we just sent);
 448     -- hence, we loop here.
 449     while true do
 450       simgrid.info("Starting to wait. My id: " .. my_node.id)
 451       task = my_node.comm_recv:wait(timeout)
 452       simgrid.info("Finished to wait. My id: " .. my_node.id .. " ask_to is " .. ask_to)
 453       my_node.comm_recv = simgrid.task.irecv(my_node.id)
 454
 455       if not task then
 456         -- failed to receive the answer
 457         simgrid.info("Task not received - is null?")
 458         return nil
 459       else
 460         -- a task was received: is it the expected answer?
 461         if task.type ~= "get predecessor answer" then
 462           -- this is not our answer
 463           simgrid.info("Task is NOT 'get predecessor answer'")
 464           handle_task(task)
 465         else
 466           -- this is our answer
 467           -- FIXME make sure the message answers to this particular request
 468           --simgrid.info(task.answer)
 469           for i,v in pairs(task) do
 470               print(my_node.id, i, v)
 471           end
 472           simgrid.info("Task is answer for predecessor! The answer is: ")
 473           if (task.answer) then print("NIL!\n") else print("Not NIL\n") end
 474           return task.answer
 475         end
 476       end
 477     end
 478   end
 479
 480   return successor
 481 end
 482
 483 -- Checks the immediate successor of the current node.
 484 function stabilize()
 485   local candidate
 486   local successor = my_node.fingers[1]
 487   if successor ~= my_node.id then
 488     simgrid.info("Getting remote predecessor from ".. successor)
 489     candidate = remote_get_predecessor(successor)
 490     simgrid.info("Received ".. candidate .. " as candidate")
 491   else
 492     candidate = my_node.predecessor
 493   end
 494
 495   simgrid.info("Still stabilizing")
 496   -- candidate might become my new successor
 497   if candidate ~= nil and is_in_interval(candidate, my_node.id + 1, successor - 1) then
 498     simgrid.info("I'm updating my successor to " .. math.tointeger(candidate))
 499     my_node.fingers[1] = math.tointeger(candidate)
 500
 501     -- If candidate is not my_node.id, then I should notify candidate that I'm here.
 502     -- (So this node updates it's predecessor to me)
 503     --remote_notify(candidate, my_node.id)
 504   end
 505
 506   simgrid.info("Successor: " .. successor .. " and my id: " .. my_node.id)
 507   -- If candidate is nil, this means that our successor has no predecessor.
 508   -- So we should tell him about us...
 509   -- TODO: I think a host that receives a message could automatically add
 510   -- this other node as a predecessor if it doesn't have any... needs to
 511   -- be implemented somewhere else, not here.
 512   if candidate == nil and successor ~= my_node.id then
 513     remote_notify(successor, my_node.id)
 514   end
 515 end
 516
 517 -- Notifies the current node that its predecessor may have changed
 518 -- - candidate_predecessor: the possible new predecessor
 519 function notify(candidate_predecessor)
 520   if my_node.predecessor == nil or is_in_interval(candidate_predecessor,
 521       my_node.predecessor + 1, my_node.id - 1) then
 522     simgrid.info("Updated my predecessor to " .. candidate_predecessor)
 523     my_node.predecessor = math.tointeger(candidate_predecessor)
 524   end
 525 end
 526
 527 -- Notifies a remote node that its predecessor my have changed.
 528 -- - notify_to
 529 -- - candidate the possible new predecessor
 530 function remote_notify(notify_to, candidate_predecessor)
 531
 532   simgrid.info("Updating someone else's predecessor (id: " .. notify_to .. " predecessor to ".. candidate_predecessor .. ")")
 533   local task = simgrid.task.new("", comp_size, comm_size)
 534   task.type = "notify"
 535   task.request_id = candidate_predecessor
 536   task:dsend(notify_to)
 537 end
 538
 539 -- Refreshes the finger table of the current node,
 540 -- one finger per call.
 541 function fix_fingers()
 542
 543   local i = math.tointeger(my_node.next_finger_to_fix)
 544   local id = find_successor(math.tointeger(my_node.id + 2^i))
 545   simgrid.info("Called fix_fingers(). Next finger to fix: " .. i .. " and I will check " .. my_node.id + 2^i .. ". Request returned " .. id)
 546
 547   if id ~= nil then
 548     if id ~= my_node.fingers[i] then
 549       my_node.fingers[i] = id
 550       simgrid.info("fix_fingers: Updated finger " .. i .. " to " .. id)
 551     else
 552       simgrid.info("fix_fingers: id is " .. id)
 553     end
 554     my_node.next_finger_to_fix = (i % nb_bits) + 1
 555   end
 556 end
 557
 558 -- Checks whether the predecessor of the current node has failed.
 559 function check_predecessor()
 560   -- TODO
 561 end
 562
 563 -- Performs a find successor request to an arbitrary id.
 564 function random_lookup()
 565
 566   find_successor(1337)
 567 end
 568
 569 simgrid.platform(arg[1] or "../../msg/msg_platform.xml")
 570 simgrid.application(arg[2] or "../../msg/chord/chord90.xml")
 571 simgrid.run()
 572