Loading...
To get the real time directions from source to destination based on path and traffic conditions.
Latency is the most important requirement. Obviously availability/reliability as well but we will prioritize latency first.
We are storing something like lat/long in some geocoding experience. We also wanna track the user's location, and give them the route based on traffic and destination.
Good thing is we can store the full map in a graph like structure which will be around 5 terabytes of storage.
We want to have a route micro-service and a location micro-service.
We can use polling at PUT https://google.com/map/:id/pol to give our location to our server. The server will respond with a 400 error or return a success with 200 status.
And we can use https://google.com/map/:id/dir to get the route from points A to B. The server will return a 400 error or a 200 success with something like
{
route_id,
map_image: url,
created_at,
vector_data
}
Well the data structure we are using will resemble a graph. Imagine we have a grid that we have created and each grid has several other grids until the smallest grid block. Once we are trying to get the direction from one grid block to the next grid block we can use djkstras for shortest path etc. Assuming we use traffic information as well, maybe the weights in each path can change therefore changing our result.
But since the data structure is like this we will use a graph database, and we can have a cache based on LRU on these routes. This database can also be sharded based on geographical location to reduce latency as we scale, since most locations will be the in same database bucket like this.
For our location service we want to use something like cassandra DB which is a nosql database optimized for write latency. So we can periodically update this traffic info here. Then have a streaming service like aws kinesis to stream this data to a mongodb traffic database which will be more optimized for reads, to be used from our route service in real time.
Well the data structure we are using will resemble a graph or a quadtree. Imagine we have a grid that we have created and each grid has several other grids until the smallest grid block. Once we are trying to get the direction from one grid block to the next grid block we can use djkstras for shortest path etc. Assuming we use traffic information as well, maybe the weights in each path can change therefore changing our result.
But since the data structure is like this we will use a graph database, and we can have a cache based on LRU on these routes. This database can also be sharded based on geographical location to reduce latency as we scale, since most locations will be the in same database bucket like this.
For our location service we want to use something like cassandra DB which is a nosql database optimized for write latency. So we can periodically update this traffic info here. Then have a streaming service like aws kinesis to stream this data to a mongodb traffic database, to be used from our route service in real time.
The route service also interacts with an amazon S3 bucket, what it will do is create images of the routes which can render streets etc of the map, and cache these in a pull based content delivery network for quick access by users who hit our server. This is important because it will reduce latency, as our server will return the image of the route, plus the actual vector data that that can then be mapped onto the image on the client side. Instead of our client having to load a map of the world etc based on just pure vector data, it will have an image plus the vector data to map onto that image
The client makes a request to the api gateway. From here we route the request to the proper microservice. We have a load balancer that uses weighted round robin to distribute the load. Route service is used to get the actual route info while location service is to just update our current location, so for location service we can use polling or websockets. Our location service will use a cassandra db to constantly write traffic updates. From there streaming those updates to a different no sql database thats optimized for read latency. Our Route service will interact with this no sql database to get traffic data and will also interact with the graph db cache to get the routes, if we have a cache miss on our LRU cache, we then pull the actual route information from our graph database. Then we simply return the results to our user.
The route service also interacts with an amazon S3 bucket, what it will do is create images of the routes which can render streets etc of the map, and cache these in a pull based content delivery network for quick access by users who hit our server.
Our amazon S3 bucket, what it will do is create images of the routes which can render streets etc of the map, and cache these in a pull based content delivery network for quick access by users who hit our server. This is important because it will reduce latency, as our server will return the image of the route, plus the actual vector data that that can then be mapped onto the image on the client side. Instead of our client having to load a map of the world etc based on just pure vector data, it will have an image plus the vector data to map onto that image
Our message queue will be using something like aws kinesis to offload update a seperate database that is less queried than our cassandra that is real time updated. Therefore allowing our route service to pull from this seperate database when it needs to. This will reduce consistency across live traffic updates but reduce latency for our app.
Explain any trade offs you have made and why you made certain tech choices...
Our message queue will be using something like aws kinesis to offload update a seperate database that is less queried than our cassandra that is real time updated. Therefore allowing our route service to pull from this seperate database when it needs to. This will reduce consistency across live traffic updates but reduce latency for our app.
Using a aws bucket plus cdn to store images of different parts of the map is a hacky way of reducing latency. The other method would have just been to return vector data and have clients load that data but depending on their phone type / model, this could take much longer on client side
We have SPOF in this app, we need more load balancers, databased aws buckets etc. We can also incorporate something like zookeeper to keep track of which systems are running using heart beats, and routing to the correct load balancer if any other load balancers are down.
Since our databases are nosql based, we will have some data like traffic data, be inconsistent in that they won't be ACID compliant. But this is a good tradeoff because the data will likely still be very relevant with lower latency.
Our current methdo used djisktras to find the path between two points, and this can be simplistic. Using machine learning instead of a simple djisktras algorithm to predict traffic flow based on past patters like rush hour etc, instead of just finding shortest path plus current traffic data.
We have SPOF in this app, we need more load balancers, databased aws buckets etc. We can also incorporate something like zookeeper to keep track of which systems are running using heart beats, and routing to the correct load balancer if any other load balancers are down.
Since our databases are nosql based, we will have some data like traffic data, be inconsistent in that they won't be ACID compliant. But this is a good tradeoff because the data will likely still be very relevant with lower latency.
Using machine learning instead of a simple djisktras algorithm to predict traffic flow based on past patters like rush hour etc, instead of just finding shortest path plus current traffic data.