examples/lua/chord/chord.lua

   1 -- A SimGrid Lua implementation of the Chord DHT
   2
   3 require("simgrid")
   4
   5 nb_bits = 24
   6 nb_keys = 2^nb_bits
   7 comp_size = 0
   8 comm_size = 10
   9 timeout = 50
  10 max_simulation_time = 1000
  11 stabilize_delay = 20
  12 fix_fingers_delay = 120
  13 check_predecessor_delay = 120
  14 lookup_delay = 10
  15
  16 -- current node (don't worry, globals are duplicated in each process)
  17 my_node = {
  18   id = my_id,
  19   next_finger_to_fix = 1,
  20   fingers = {},
  21   predecessor = nil,
  22   comm_recv = nil
  23 }
  24
  25 -- Main function of each Chord process
  26 -- Arguments:
  27 -- - my id
  28 -- - the id of a guy I know in the system (except for the first node)
  29 function node(my_id, known_id)
  30
  31   simgrid.debug("Hello, I'm a node with id " .. my_id .. " and I know " .. known_id)
  32
  33   -- join the ring
  34   local success = false
  35   if known_id == nil then
  36     -- first node
  37     create()
  38     success = true
  39   else
  40     success = join(known_id)
  41   end
  42
  43   -- main loop
  44   if join_success then
  45
  46     local now = simgrid.get_clock()
  47     local next_stabilize_date = now + stabilize_delay
  48     local next_fix_fingers_date = now + fix_fingers_delay
  49     local next_check_predecessor_date = now + check_predecessor_delay
  50     local next_lookup_date = now + lookup_delay
  51
  52     local task
  53     my_node.comm_recv = simgrid.task.irecv(my_node.id)
  54
  55     while now < max_simulation_time do
  56
  57       task = simgrid.comm.test(node.comm_recv)
  58
  59       if task then
  60         -- I received a task: answer it
  61         my_node.comm_recv = simgrid.task.irecv(my_node.id)
  62         handle_task(task)
  63       else
  64         -- no task was received: do periodic calls
  65         if now >= next_stabilize_date then
  66           stabilize()
  67           next_stabilize_date = simgrid.get_clock() + stabilize_delay
  68
  69         elseif now >= next_fix_fingers_date then
  70           fix_fingers()
  71           next_fix_fingers_date = simgrid.get_clock() + fix_fingers_delay
  72
  73         elseif now >= next_check_predecessor_date then
  74           check_predecessor()
  75           next_check_predecessor_date = simgrid.get_clock() + check_predecessor_delay
  76         elseif now >= next_lookup_date then
  77           random_lookup()
  78           next_lookup_date = simgrid.get_clock() + lookup_delay
  79
  80         else
  81           -- nothing to do: sleep for a while
  82           simgrid.process.sleep(5)
  83         end
  84       end
  85       now = simgrid.get_clock()
  86     end -- while
  87
  88     -- leave the ring
  89     leave()
  90   end
  91 end
  92
  93 -- This function is called when the current node receives a task.
  94 -- - task: the task received
  95 function handle_task(task)
  96
  97   local type = task.type
  98
  99   if type == "find successor" then
 100
 101     -- is my successor the successor?
 102     if is_in_interval(task.request_id, my_node.id + 1, my_node.fingers[1]) then
 103       task.type = "find successor answer"
 104       task.answer = my_node.fingers[1]
 105       task:dsend(task.answer_to)
 106     else
 107       -- forward the request to the closest preceding finger in my table
 108       task:dsend(closest_preceding_node(task.request_id))
 109     end
 110
 111   elseif type == "get predecessor" then
 112     task.answer = my_node.predecessor
 113     task:dsend(task.answer_to)
 114
 115   elseif type == "notify" then
 116     -- someone is telling me that he may be my new predecessor
 117     notify(task.request_id)
 118
 119   elseif type == "predecessor leaving" then
 120     -- TODO
 121
 122   elseif type == "successor_leaving" then
 123     -- TODO
 124
 125   elseif type == "find successor answer" then
 126     -- ignoring
 127
 128   elseif type == "get predecessor answer" then
 129     -- ignoring
 130
 131   else
 132     error("Unknown type of task received: " .. task.type)
 133   end
 134 end
 135
 136 -- Returns whether an id belongs to the interval [a, b[.
 137 -- The parameters are normalized to make sure they are between 0 and nb_keys - 1.
 138 -- 1 belongs to [62, 3].
 139 -- 1 does not belong to [3, 62].
 140 -- 63 belongs to [62, 3].
 141 -- 63 does not belong to [3, 62].
 142 -- 24 belongs to [21, 29].
 143 -- 24 does not belong to [29, 21].
 144 function is_in_interval(id, a, b)
 145
 146   -- normalize the parameters
 147   id = id % nb_bits
 148   a = a % nb_bits
 149   b = b % nb_bits
 150
 151   -- make sure a <= b and a <= id
 152   if b < a then
 153     b = b + nb_keys
 154   end
 155
 156   if id < a then
 157     id = id + nb_keys
 158   end
 159
 160   return id <= b
 161 end
 162
 163 -- Attemps to join the Chord ring.
 164 -- - known_id: id of a node already in the ring
 165 -- - return value: true if the join was successful
 166 function join(known_id)
 167
 168   local successor = remote_find_successor(known_id, my_node.id)
 169   if successor == nil then
 170     return false
 171   end
 172
 173   my_node.finger[1] = successor
 174   return true
 175 end
 176
 177 -- Returns the closest preceding finger of an id with respect to the finger
 178 -- table of the current node.
 179 -- - id: the id to find
 180 -- - return value: the closest preceding finger of that id
 181 function closest_preceding_node(id)
 182
 183   for i = nb_bits, 1, -1 do
 184     if is_in_interval(my_node.fingers[i].id, my_node.id + 1, id - 1) then
 185       -- finger i is the first one before id
 186       return my_node.fingers[i].id
 187     end
 188   end
 189 end
 190
 191 -- Finds the successor of an id
 192 -- id: the id to find
 193 -- return value: the id of the successor, or -1 if the request failed
 194 function find_successor(id)
 195
 196   if is_in_interval(id, my_node.id + 1, my_node.fingers[1]) then
 197     -- my successor is the successor
 198     return my_node.fingers[1]
 199   end
 200
 201   -- ask to the closest preceding finger in my table
 202   local ask_to = closest_preceding_node(id)
 203   return remote_find_successor(ask_to, id)
 204 end
 205
 206 -- Asks a remote node the successor of an id.
 207 -- ask_to: id of a remote node to ask to
 208 -- id: the id to find
 209 -- return value: the id of the successor, or nil if the request failed
 210 function remote_find_successor(ask_to, id)
 211
 212   local task = simgrid.task.new("", comp_size, comm_size)
 213   task.type = "find successor"
 214   task.request_id = id
 215   task.answer_to = my_node.id
 216
 217   if task:send(ask_to, timeout) then
 218     -- request successfully sent: wait for an answer
 219     while true do
 220       task = simgrid.comm.wait(my_node.comm_recv, timeout)
 221       my_node.comm_recv = simgrid.task.irecv(my_node.id)
 222
 223       if not task then
 224         -- failed to receive the answer
 225         return nil
 226       else
 227         -- a task was received: is it the expected answer?
 228         if task.type ~= "find successor answer" or task[request_id] ~= id then
 229           -- this is not our answer
 230           handle_task(task)
 231         else
 232           -- this is our answer
 233           return task.answer
 234         end
 235       end
 236     end
 237   end
 238
 239   return successor
 240 end
 241
 242 -- Asks a remote node its predecessor.
 243 -- ask_to: id of a remote node to ask to
 244 -- return value: the id of its predecessor, or nil if the request failed
 245 function remote_get_predecessor(ask_to)
 246
 247   local task = simgrid.task.new("", comp_size, comm_size)
 248   task.type = "get predecessor"
 249   task.answer_to = my_node.id
 250
 251   if task:send(ask_to, timeout) then
 252     -- request successfully sent: wait for an answer
 253     while true do
 254       task = simgrid.comm.wait(my_node.comm_recv, timeout)
 255       my_node.comm_recv = simgrid.task.irecv(my_node.id)
 256
 257       if not task then
 258         -- failed to receive the answer
 259         return nil
 260       else
 261         -- a task was received: is it the expected answer?
 262         if task.type ~= "get predecessor answer" then
 263           -- this is not our answer
 264           handle_task(task)
 265         else
 266           -- this is our answer
 267           -- FIXME make sure the message answers to this particular request
 268           return task.answer
 269         end
 270       end
 271     end
 272   end
 273
 274   return successor
 275 end
 276
 277 -- Checks the immediate successor of the current node.
 278 function stabilize()
 279
 280   local candidate
 281   local successor = my_node.fingers[1]
 282   if successor ~= my_node.id then
 283     candidate = remote_get_predecessor(successor)
 284   else
 285     candidate = my_node.predecessor
 286   end
 287
 288   -- this node is a candidate to become my new successor
 289   if candidate ~= nil and is_in_interval(candidate, my_node.id + 1, successor -1) then
 290     my_node.fingers[1] = candidate
 291   end
 292
 293   if successor ~= my_node.id then
 294     remote_notify(successor, my_node.id)
 295   end
 296 end
 297
 298 -- Notifies the current node that its predecessor my have changed
 299 -- - candidate_predecessor: the possible new predecessor
 300 function notify(candidate_predecessor)
 301
 302   if my_node.predecessor == nil or is_in_interval(candidate_predecessor,
 303       my_node.predecessor + 1, my_node.id - 1) then
 304     my_node.predecessor = candidate_predecessor
 305   end
 306 end
 307
 308 -- Notifies a remote node that its predecessor my have changed.
 309 -- - notify_to
 310 -- - candidate the possible new predecessor
 311 function remote_notify(notify_to, candidate_predecessor)
 312
 313   local task = simgrid.task.new("", comp_size, comm_size)
 314   task.type = "notify"
 315   task.request_id = candidate_predecessor
 316   task:dsend(notify_to)
 317 end
 318
 319 -- Refreshes the finger table of the current node.
 320 function fix_fingers()
 321
 322   local i = my_node.next_finger_to_fix
 323   local id = find_successor(my_node.id + 2^i)
 324   if id ~= nil then
 325     if id ~= my_node.fingers[i] then
 326       fingers[i] = id
 327     end
 328     my_node.next_finger_to_fix = (i % nb_bits) + 1
 329   end
 330 end
 331
 332 -- Checks whether the predecessor of the current node has failed.
 333 function check_predecessor()
 334   -- TODO
 335 end
 336
 337 -- Performs a find successor request to an arbitrary id.
 338 function random_lookup()
 339
 340   find_successor(1337)
 341 end
 342
 343 simgrid.platform(arg[1] or "../../msg/msg_platform.xml")
 344 simgrid.application(arg[2] or "../../msg/chord/chord90.xml")
 345 simgrid.run()
 346