educative.io

Lost Updates to QuadTree

Courses
,
#1

To update a driver to its new location, we must find the right grid based on the driver’s previous location. If the new position does not belong to the current grid, we have to remove the driver from the current grid and move/reinsert the user to the correct grid

So we send locationInfo - {old_lat,old_lang,new_lat,new_lang} from Driver Location Server to QuadTreeServer to update the driver location and move him/her to the right grid. What happens if the locationInfo is lost due either Driver Location Server going down and communication backend to the QuadServer going down. I understand we will get the updates every 3 seconds but we need all the locationInfo to move the driver to the right grid otherwise next time the Driver Location Server sends the locationInfo we will have the same driver in 2 different grid points.

E.g.

  1. Driver 1 is in Loc1 which is represented by Grid1
  2. Driver 1 moves to Loc2 which is represented by Grid2
  3. Driver Location Server communicates to Quad Server to move Driver 1 from Grid1 and moved to Grid2
  4. Driver 1 moves to Loc3 which is represented by Grid3.
  5. Driver Location Server fails to communicate to QuadGridServer
  6. Driver 1 moves to Loc4 which is represented by Grid4.
  7. Driver Location Server communicates to Quad Server to move Driver 1 from Grid3 and moved to Grid4
  8. Error! - Possible outcome Driver 1 exists on both Grid2 and Grid 4

How should we handle this scenario. Maybe have a cleanup job which is trigger when an error is encountered

2 Likes
#2

Thank you for reaching out to us. The author of this course will get back to you soon.

#3

I would assume that the QuadTree would also maintain the list of DriverIds and the current Grid. That way when you update, you would only need to send the current Grid. The server would look up the Grid for the DriverId then update it with the new Grid.

Anyway, if we did keep the old Grid, I would only update it after getting an acknowledgement from the QuadTree server. So in your example, the old location would still be Grid2 since it never contacted the QuadTree. So when Grid4 is updated, it’s sending Grid2 as the old id, which is what the QuadTree server still has.

I still think it’s best to let the QuadTree server keep track of the current location for each driver. Then external clients only need to specify what the NEW current location is.

2 Likes