System requirements

Functional:

+Users are able to use an address, to set a location.

+ users get a list of routes to the destination.

+ users are able to follow the route and get a new route if they change it. they're able to see delays in the route.

+ Users should be able to select different transportation methods (walking, bycicle, car).

Non-Functional:

+ reliability

+ scalability

+ consistency

out of scope:

+ being able to review/see reviews of places

+ Analytics

+ Authentication

Capacity estimation

+ we expect the system to be able to support hundreds of millions of users.

+ routes should be roughly a few hundred kilometers (same country)

API design

/api/places?keywords=&coordinates [GET]

req:{ a list of keywords to match a place.

coordinates to run a query }

response {

a list of places. the places contain places details and coordinates

}

/api/route [GET]

req: {

coordinates

}

response: {

route steps (a list of route steps for the user to follow

}

/api/navigation [POST] , streaming

req: {

current location

}

response {

traffic update

}

Database design

Table Places

PlaceId

Location

Place Name

Place Picture

Index by location, place name

Table Navigations

NavigationId

- this is a list of all the places that a user navigated to

UserId (or user identifier)

No index, this is more for historic services

High-level design

Request flows

1) Users send a request to search for a place. Place service does a matching based on the user location (this is a delimited area based on the user app, they can zoom-in or zoom-out). Then the service runs another search based on keywords, and returns the potential best candidates. Please notes that place can include popular places like restaurants, and destinations. This should use either elastic search (separate DB) or it could be on the same DB. I prefer having it on the same DB, a technology like spanner would allow us to have the places table and a separate index for searches.

2) Users get a route to a specific place.

The route service will come up with a list of potential routes for the trip. Then the orchestration service will call the traffic service with the routes. The traffic service will update those routes and will update ETAs. The route service will then re-rank them based on total ETA.

3) Users post their navigation details which are sent to the navigation DB. Users also will get updates from the traffic service for their ETAs.

Detailed component design

Route service is a smart dijkstra. Smart meaning that it tries to reduce the number of instructions for a user (nobody wants to navigate 100 small streets over having to navigate a single freeway if the difference is one minute, for example). The smart dijkstra will give different responses based on the transportation method, e.g. if walking, we can cross over parks, but if driving, we have to follow transportation rules).

Traffic service has real time updates from users. IF we think of the response of route service as a graph with edges and points. Each edge in the response, will have an ETA. The traffic service will determine which edge does a certain point belong to and update the ETA. To do this we can look at expected speed for the edge, and actual average speed of the current users on that edge.

We can expect this DB to be read-intense, since more users will query over the road than users updating the road. The number of users over a certain edge is limited (because it's physically limited over the real world).

To alleviate hotspots we can do this from the DB, for example, instead of storing a freeway as a single entry, we could have multiple entries for the same freeway.

This is a completely stateless design, so, we can rely on a random load balancer from client -> orchestration server.

Trade offs/Tech choices

Having an orchestration server at the expense of latency. Allows us to have all the orchestration logic in the server-side, which allows us to push updates to our algorithms faster.

If we let the client have all the orchestration logic, we could run into issues since clients can spend years without updating the app.

Having multiple databases for pretty much the same thing (places and routes). This means that all Databases need to keep in sync, which is at the cost of more engineering maintenance needed.

Failure scenarios/bottlenecks

what happens if we have too many users over an edge?

we expect the division of edges to be enough so that users will never experience this. a machine should always be able to handle the requests of a single edge.

what happens if the user loses the connection for traffic?

we don't need to interrupt the user with a route. in the client we should have an internal db that shows all the steps needed to get from point A to point B. We should try to recover by restarting a connection, we can use exponential retry and after `x` retries we let the user know that we lost the connection to the server. On the client side, the number of updates is different depending on the transportation type. If it's a car, we need to constantly look for updates, but if it's walking, then we shouldn't worry too much since less things can suddenly interrupt our route.

what happens if there's an accident or a sudden route closure?

our traffic service will constantly get updates. the orchestration service should decide if the ETA has changed significantly enough so that we should query the route service.

Future improvements

use machine learning instead of a smart dijkstra.

create monitoring tools to make sure each server is well provisioned to handle the requests for a given edge.