Hi everyone!! Welcome to CodeKarle. My
name is Sandeep, and in this video we'll go over how do we design a navigation
application like Google Maps. Now let's go over some Functional and Non
Functional Requirements(NFRs) that we want this platform to support.
So the very first thing is when a person wants to move from point A to point B, this
platform should be able to give them a couple of information .
1) What is the route that they should follow 2) Given that route how much distance
they'll have to cover and how much time it will take. As an enhanced variant we
could also build a system in which we show them 2-3 routes and then let them
choose that they want to minimize the distance or minimize the time.
3) The next thing is that it should have a very pluggable model. So let's say we make a
very basic design which just has no traffic data or anything of that sort.
Now let's say if you want to plug in traffic information it should be easy
enough to add it. Now post that let's say if you want to add information about
weather or accidents or construction going on somewhere or road blockages or
something of that sort, it should have a very easy way to input this data and not
make a change in whole of the architecture. So that's the main idea of making a pluggable.
4) There's one more thing that we'll cover in a very brief
thing, that is basically how do you identify roads. So there are two three
ways in which we can identify new roads. So one very basic or the most efficient
way is to just ask government sources to give us all the information about
all the roads data that they have. Now they might not have all the data but at
least we'll have a good starting point. Now beyond that we can capture a lot
of organic data. So let's say if a lot of users are going on to a place or a route
kind of a thing which we don't identify as a road, then we can easily say that it
there is a road that we don't know of and we can kind of onboard that Road
onto our system. Now we can use some data like number of people traveling on it,
which sides are they traveling to, what is the volume of traffic, what is the
speed and correlate that with the existing roads that we have and try to
even come up with how wide the road is!! Is it a single lane road or if it's a
four lane/six lane kind of a road. All of those information could be figured
out. But we will still not go into this in much depth over the video. Mainly what we'll focus on is How do we efficiently find the route between two points? Now coming to the non-functional requirements the very first thing is the system should be always Available. This should not go down.
The next thing is it should have a good enough accuracy. Now let's say if you are
not giving the very best route but if even if you are giving a good enough
route that should be okay, unless it's not a terrible route, okay. And it should
not be too slow so let's say if it takes 1 second/2 seconds/3 seconds to
do all the calculations and come up with output that should be okay. It's not that
it should respond back in a millisecond with the best route between two points.
That's a bit too much to ask for, a couple of seconds one, two, three seconds
should be okay. But it should not be too slow. Like it should not take 15 seconds to
come back with the response, okay!! Coming to the scale, again I do not know
if these numbers are authentic, but from what I've heard and read, Google Maps
roughly has a billion MAU (Monthly Active Users) and these users generally access
Google Maps a couple of times in a day or maybe a couple of times in a week at least. What that means is we'll probably
have roughly five to ten billion requests coming in a month for time,
distance and route between two points from users. Then there are also five million
companies which use Google map so companies could be companies like Uber
who are using Google Maps to come up with the Navigation and Pricing System,
or it could be smaller companies which have a very similar use case.
But that means that we need to keep these things in mind that we have a very large volume
of users who are coming into system who will be using this platform and design it accordingly. now building this Navigation App is a very hard problem to
solve. Not because of the kind of Algorithms that we'll use. But more because
of the kind of requirements this has. So for example, if we try to calculate the
number of roads in the world there are various theories, which you know come up
with various numbers. In general people cannot claim that there are somewhere
close to 50-100 million roads in the world. It could be you know even a much larger number.
Now if we try to model it as a graph it would probably have somewhere
close to 50 million vertexes and maybe you know hundreds of millions of edges
if we divide the roads into multiple chunks and all of that, right. So that is a
very very massive data set.Now a lot of companies don't even have access to this
kind of a data, where in what road is connecting from where to where. That kind
of information is kind of non-existent throughout the whole world and there is
no single place where you can fetch that, which makes it a very hard problem
to build an navigation system like this. The next thing is, it is very
hard to even quantify a lot of attributes that will impact the ETA.
For example traffic and weather condition and Road quality. Things like these are
very hard to quantify so there is not a very easy mathematical formula that you
can come up with to calculate the ETA that will be required to cover a
particular distance. One more challenge this is, a lot of things into the whole
road systems are very unpredictable. There could be and a random accident
happening somewhere, there could be a road closure due to any kind of reason
and those things are not really predictable and that's the main reason
why you know a lot of companies have not been able to build this kind of system successfully. We will be using an ideology of Dynamic Programming while we
try to solve this problem. So basically what we will do is, we will try it for a
very small area, and then we will try to solve it for a larger area, and then even
larger area and then across cities and countries and so on and so forth. So
before we get started let me introduce you a concept called "Segment". Now this
is not an industry standard term I just made up this name on my own, so just keep
that in mind. A Segment is basically a small area that is small enough that we
can easily operate on to it. Think of it like this we can have segments of one
kilometer by one kilometer throughout the globe. So let's just say if you have
a city, something like this, what we'll do is we'll divide the city into multiple
segments. Now ideally there will be a lot more segments than what we are drawing
but for understanding this should be good enough, okay. Now the idea behind
these segments is that it will have four coordinates which are the four corners
of a Segment, through which we can identify the segment boundaries and each
segment would have an identifier. You can say this segment s1, this is s2, something
of that sort. Now the thing with segments is whether a point lies within a
particular segment? - is something we should be easily be able to calculate.
So for example think of it like a coordinate system you have these x axis
and y axis, this is your point (0,0), this is your point (0,1), this is
your point (1,0) and let's say this is your point (1,1). This is your
square of one each, right. Now whether a point lies within this or outside this we can
easily identify based on what its coordinates are right and similarly for
this based on its XY coordinates we should be able to identify whether this
lies in this particular segment or not. So what we will try to do is each user
will try to map it to some segments basis their coordinates, right! Now one
good thing about these segments is because these are functions of Lat-Long,
we should easily be able to identify some approximate distance
between two segments. So let's just say if you want to identify this distance
between these this segment and this segment, right. So basically let's say if we come up with the center points of both of these and these are two
lat/longs we can easily find the distance between (aerial distance) between
these two points. We use this in the later sections but it's a very easy
mathematical calculation given two lat/longs, find the aerial distance
between these, right? Now what we'll actually do is, let's say the whole globe
for example, we will actually divide the whole globe into multiple
segments some of the segments would just have water and nothing else but most of
the segments would have some localities and we will be solving for one segment
each and then we will extend the solution for multiple segments segments
which will then cut across multiple cities and countries and whatnot, okay!!
Now the way we model the road network is like a graph. So think of two points
let's say this is point A and this is point B, and then the road between these
two points, okay. So this becomes one vertex(A), this becomes another vertex(B) and
the road between them can be represented as an edge. Now each road would have
a weight. Now will not have one weight like you normally have in usual graphs,
will have multiple weights. so let's say this road is of length 2 kilometers so one of
the weights on this road would be 2 We could have a bit more
weights along with that. We would have a traffic weight, we could have a
time-based weight. So let's just say we come up with the average number thing in
general it takes 150 seconds to cross this road, so 150 becomes another weight.
okay! So this is how we represent a particular road and similarly there could
be other weights that we can add. Now a road, even though it looks like a
non-directional thing, but it is actually are directed relationship. Normally
how would you represent it? - you'll say that this one Road from A to B which is 2
kilometers long, takes 150 seconds. There's also another road which is from B to A,
which is again two kilometers long, but this one probably takes 200 seconds
to cover, right! Why do we need a directed relationship here? - Firstly in order to
handle if there is a different ETA or different traffic pattern or something
of that sort. Plus more importantly, if this says that it takes infinite amount
of time to reach here that's basically a way to say that it's a one-way Road. Only
you can go from point A to point B but not from B to A, right! So we can use all
of these ways to track various things like one ways or various different kinds
of roads. Now even though if it's a directed graph but for all the like
talking within this video I will draw a single line thinking of it as a non
directed relationship, because it makes the drawing easier and explanation
easier, but when you are actually going to implement it, you will implement it as
a directed relationship. Now let's look at what happens when you want to find
the distance between two points within a segment or even ETA or something of that
sort? So let's say this is a graph of all the roads, within a particular segment
and there are these ABCDEFGH... are the junctions or the points where you might
want to start or end from, and everything else is basically in edge. And
edges could have weights, assuming that all the edges have certain weight. Let's say this
edge has a weight of, first attribute is the length which could mean 2 kilometers the
next attribute might say that how much time it takes to cover that 2 kilometer. This would have a length of 5 kilometers and would take 700 seconds to
cover that. Now let's say if you want to go from point A to point C, how
can we go? - There could be multiple routes. So one of the routes
could be from A to B to C. There could be another route from A to B to E to C
there could be another route from A to I to H to G to B to C and there could be
another, a lot more number of routes. How do you find the best route
from going from point A to point C? This is a very standard problem in the
Graph Data Structures, there are various algorithms to solve it. We can use
anything like a Dijkstra or a Bellman Ford Algorithm to come up with the shortest
path between point A to point C. Once you have calculated this and we
might as well decide to cache it. Because within a segment, it's good to
know how can you move from point A to point B. Normally what you would do is
you would run something like a Floyd-Warshall Algorithm, which calculates the
shortest path between all possible edges in all possible vertexes within a
particular segment and then store that information so that you do not have to
recalculate it. So what it will end up being is, there are these all
normal roads which are edges and then there could be a calculated edge also
which says that, for A to C, the shortest path takes ten kilometers, it takes two
thousand seconds and it is via Point A then B then E then C, something of
that sort could be a calculated edge as an output of Floyd-Warshall Algorithm,
which can be stored in another Data Store which can then be looked up if you
want to quickly look at how much time does it take from reaching a point A to
point C. Now what we looked at earlier was given a junction A and given a
junction C how do we calculate the shortest distance between those two
junctions. What if the point with what we are looking at is not really a junction
which is the meeting point of two roads but any random point in the globe which
just comes on a particular road. Let's say that point is X, okay. And now we want
to find the shortest distance between X and C. What that translates is basically
find this distance (X->A), lets you call it . Find this distance (X->B) let's say we call it J.
Basically find that two short... two or three closest junctions from that point.
Normally if that is on a road it'll just be two junctions right, and find the
shortest distance from those two junctions. So whatever is the distance
from A to C and B to C, add I and J respectively into that and then
whichever is the shortest one that becomes your answer. Now if you want to
extend it further and say that I want to find out the distance between X and Y? -
What you basically mean to solve is A to C, the distance between A to C,
the distance between B to E, and then these two good respective distances
add it. So this (C->Y) is let's say i`, this(E->Y) is j` So what you want to do is a comparission
between [ i + i` + distance(A,C)] or this the distance of [ j + j` + distance (B,E) ] So this is how you
can handle any point even if it is not a junction. Now whenever you're calculating remember we looked at that we can use a
Floyd-Warshall Algorithm and then calculate all the possible distances
within a segment, right. What we should also do at that time is look at what all
possible exits are there some a Segment. Why that's important? we'll come to.
Let's say there are these two roads which are exiting a particular segment. Let's
say this is a Exit 1(E1). Let's say this is a Exit 2(E2). And the segment Id
is let's say S1. So what we say is this particular Junction is S1E1 and this
particular Junction is S1E2. What we'll also calculate is distance of each
Junction not from just other junctions but also from these two points. So we
will also know that what is the shortest route from reach from C to S1E1
and from C to S1E2. And we'll store this also as a cached information. Now
let's come to how do we solve it across multiple segments. Now let's say if you
have this point A. From now on we will just look at junctions because that
makes the calculation easier okay. You want to calculate distance from point A
to point B and all these rectangles that you see are unique Segments and
these two points are in different Segments. Then how do you actually
calculate the distance between the two points and the same logic would be used
to calculate the ETA and anything between these two points okay. So what we
are essentially saying is, we have this point A and we have this point B. Now
given the lat/longs we would be able to identify an aerial distance between them.
Let's just say that the aerial distance between them is 10 kilometers, okay.
We also know that each segment is one kilometer by one kilometer in length and
width right. So what we can say is we'll at max go... so because this is 10
kilometers on aerial distance, what we can say is.. adding some buffers we will
not cross more than 20 Segments on each directions either going from North to
South or going from East to West. That 20 number is basically a buffer that you
can come up with based on your conversation with your interviewer.
But the idea is this number(10 KMs) will give us some input onto how many segments do I
want to look at. So 20 segments on the North-South side and 20 segments on East-West side is what we'll look at to come up with the optimal route from point A to point
B. Because normally what would happen is there will be millions of roads into the
world. And if you start doing a Dijkstra across the whole globe just to
calculate distance between these two points, that will be very un-optimal.
So we have to break that Dijkstra at some point in time. So this number would be used to
break that Dijkstra saying that we will not go further that beyond this point.
Now one obvious way to solve this is you have all the roads connecting the whole city
which cuts these two points as well. Run a Dijkstra across the city and then come
up with the shortest distance between point A to point B. But if you look at it
and if you look at it that way that there are probably millions of users
querying at the same time to find distance between any two points, Running
those many number of Dijkstra's Algorithms would be heavily inefficient.
So we'll do some slight optimization there. What we'll do is, there are... we'll
basically say that there are two exits out of this block(Segment having A). Basically to reach
this block(Segment having B) we need to exit this block and there are these two ways. Let's say if we have
calculated that these two are the only exists within this segment. Let's say this a
segment S1. So A belongs to S1 and these two are the exits, this is S1E1
and this is S1E2 and they have some great W 1 and W 2 let's say.
Now what we'll do is, this segment... this junction is basically having two points.
One is S1E1.. two identifiers basically, S1E1 and S2E1. this is segment ID
S2 and this is exit number one of that segment so this has another identifier
for S2. What we are saying then is this has another point on the same route
which is S2E1 and weight between them zero. similarly there'll be a lot of points.
This graph will fan out. On the other side for B,
let's say B belongs to segment S4 there are another two exits through which you
can reach B. One is S4E2 and one is this one which is S4E1 even. Now if we just connect all the exits to exits for ten blocks(Segments) on the North side,
ten blocks(Segments) on the South side, ten blocks on this side and ten blocks on that side,
we'll basically be able to come up with a crisscross of a lot of Road which connects these four points right and there'll be a lot of junctions within
that, there'll be a lot of roads, but these will be basically just entry points and
exit points of the segments. We don't really care what are... what is happening
within the segment when we are cutting across segments. Why? - because to reach
this segment we anyway need to cross all of the other segments right. Now we don't
care if this route which we are calling as let's say this is segment S6 and this
point is S6E1, this point is S6E2 Now this is basically a calculated
path from these two exit points. This exit point to that exit point basically.
This real path would look something like this right but we don't really care
what's happening within the segment. All we care about is from this point(S6E1) to this
point(S6E2), I know the distance, and I'll use that. Then from this point to this point I
know the distance I'll use that. So we'll basically be using all the exit points distances and use them as weights, and come up with this graph at runtime. Now given like ten
segments on each side, we'll probably have this graph of a couple of hundreds of
edges at max right. Now we can run a Dijkstra on this graph staying with that
what is the shortest path to go from here(A) to here(B). This Dijkstra runs on
top of the graph which was created by just entry points and exit points in
everything else, and entry point and start point and entry point and end point in the
starting and ending segments. Everything else was just a connector
from individual end point to individuals basically exits of a particular segment.
Now this is fine when we have to travel for like ten odd kilometers we can still
create a graph of these 100-200 edges and calculate. What if you want to go
inter-city? What if you want to go from City 1 to City 2 and then you
want to calculate it? Then it becomes a big trouble to... because let's say the
distance between those two city is thousand kilometers then there are
possibly thousands of segments multiple thousands of segments that you'll
look at, right. That would too complicated to run a Dijkstra at runtime. Now like we
extended the solution from one segment to multiple segments, we can basically
create a Mega-Segment, right? We can say this whole thing that you see
here is 1 Mega-Segment and there could be this exit to this Mega Segment this exit
to this Mega Segment and probably an exit here to this Mega Segment, right? And
then what we can say is, let's say you have this whole map of a country. I
know it looks terrible but let's say this is one country, what you can say this is 1
mega segment you can basically divide this country into mega segments.
And then recursively solve for it even further. Now when you were to if you are
to solve in the mega segment world you have basically converted this whole
country into possibly 50 mega segments and now if you want to go from here to
here, you basically need to just connect the exit points of individual
Mega Segments. You don't really care what is happening within a mega
segment, you don't really care what is happening within segments under those
mega segments and roads under those segments. All you care about it from my
start point how do I get to the nearest exit or all the exits of that mega
segment and from these exits of mega segments how do I get to further mega
segments recursively and then somehow reach this end point, right. Now you can
have n levels of nesting. Ideally three levels of nesting is more than enough.
Now what is the ideal size of this mega segment? - Again there is no right answer
you can come up with based on some calculation with your interview again on
this. But the idea if you still want to calculate this thing across cities or across states, this segment approach would still not scale you need to do an
abstraction on top of segments which can be represented as a Mega-Segment and
then solve it recursively. All good so far but we have not really
talked about how do we come up with the weights on an edge and how do...what all weights do we even consider? So the very first obvious weight is the amount
of distance between two points right so that is one thing that will definitely have.
Along with that we will also keep an ETA that normally under normal
traffic conditions, in the normal weather conditions, how much time does it take
for a user to go from point A to point B. Now when we have both these
information we can obviously keep a next obvious thing saying what is the average
speed of vehicles. Speed = (distance/time) so basis that will
be able to come up with an average speed. Now you might think that the next
obvious you things are weights like traffic and weather condition and all of
that but I would definitely not recommend that. Even... let's assume
this is what we have build already and now somebody comes up and asks you to
implement traffic data into this okay now if you want to add traffic as a
weight onto your edges that'll be a very very bad design. Why? - Because with an
additional attribute that you are adding you are basically changing the logic of
your underlying Dijkstra which runs on a segment, right. Now let's say tomorrow
somebody comes up asking you for a weather information you will again
change the whole logic of your Dijkstra. That piece is a bad design, okay. So ideally..
basically the set of things that a good design should entail is basically that
it should not restrict addition of new features plus each change should be
small enough and contained. It should not basically impact the whole feature.
So what we'll say is traffic and all all of those in things are basically attributes
which impact your speed okay and basis whatever your average speed is you can
calculate the ETA as a function of distance and average speed, right?
So all we'll say is traffic, weather, roadblocks all of those they'll never be weights on your
graph, okay. They would just be attributes that impact your average speed. So
average speed would be a function of traffic, it could be a function of
weather it could be a function of any number of
fields that you want. Let's say if you want to add a accident, or construction work
going on someplace or whatever you want to add. So all of those would basically
impact your average speed. Now normally you don't have to do all these fancy
things, never ever! Why? - Because it's for a company like Google Maps they know...
let's say there are hundreds of people going from point A to point B. They
anyway know how much time they took right plus a very important feature
about this kind of data is, this traffic data would always be normally
distributed. So if we want to plot, Let's say this is basically any metrics let's say
ETA of how much time it took for people to go from point A to point B on a graph
it would always look like a normal distribution, okay. What that means is you
do kwow that there is this point which most of the users are hitting and as a...
with some statistical calculations of one standard deviation from each of
these point you will be easily be able to calculate this range that normally for
most of your users at least 50-60-70% of your users, this is the
window of time that it will take. Let's say this is 5 seconds this is 7
seconds and let's say average is 6 seconds for example so statistically you can
come up with this number as a function of lot of users who are crossing the
roads. So you don't really care how much is the traffic, what is the weather, when
you anyway have this real-time information So for all the
geographies where you have people using your application, there you have organic
data from real users at this point in time so you don't really care about
traffic and all of that. Traffic and all other things will come into picture only
in places where you can either not get enough data from users or there is some
other reason why you're maybe legally not allowed to get information of users
right because of which if you don't have real data users, then is when you will
bother about using traffic and weather and all those attributes to come up
with this average speed number basis that you can even know the distance from
point A to point B, you can come up with a ETA, okay.
Now how do we quantify traffic? you cannot say that if there are 805
vehicles, it will take this much amount of time, right. The number of vehicles on
a road and things like that cannot be calculated at all. No matter how good
technology you build right. So when these things cannot be quantified how do you
use them as a measure? So what we can say is basically create multiple "Tiers".
Let's say this is traffic measurement and this is Weather Management.
All you can say is traffic is low or it is medium or it is high and whether it is
good or it is bad, right. So you will have these kind of Tiers for each of the
attributes that you have and all you can say is every time traffic goes from here(Low)
to here(Medium), it has a 20% increase onto average speed or something of that sort.
right every time traffic goes from low to medium, average speed reduces by 20
percent. Basis these transitions of traffic volume... now you can always say that
traffic is low or high based on the number of users that are probably using
your application or from some other sources, right. Let's say you have this
kind of a measure, so there are companies like Waze and all, which will give you the
kind of information that how's the weather, how is the traffic in a very
abstracted form. Now once you have this information you can calculate
average speed as a relative number from the original value calculated. so let's
say with the good weather, with the medium traffic you knew the average
speed was later 20 kilometers per hour Now if the traffic goes to high, you
kind of reduce it by 20%, so it basically becomes 16 kilometers per hour. Basis is
this kind of a calculation, you will calculate the ETA. Now as and when
inputs are coming, you are making changes into your weights on the graph. How
does it impact the overall system? So coming back to the previous drawing that
we made remember we had something called as a segment and we had lots of roads
within the segment and let's say the traffic increase we got a signal from
some third party saying traffic has increased on a particular Road. Now do
whatever you want to. Now let's say there was this one exit point and one exit
point and distance between this was some Let's say there are some X weight to this
particular theoretically calculated road. And let's say it was actually
using this particular road on which the traffic is increased, let's say it
actually was following this kind of a graph, something of that sort.
Now similarly all other roads are getting changed. So all you can say is remember
in this all the theoretically calculated roads that we have to be calculated we
were caching that what all real roads are a part of this theoretically
calculated road. Which is... it is not a real route, but a calculated edge.
So each time this thing changes, weight changes on any real road, you basically
try to infer, what all actual cached roads are impacted. And then you
basically make a change into the cached roads also. So you say that okay the time
taken initially was 10 seconds, for this path, now it has become 15. So let me
increase the value of this particular calculated road from point E1 to E2 by 5 seconds Now let's say you do this for one
segment, then what basically happens is you recursively bubble it up over a lot of cached things. So let's say if there was a mega segment who's...
who had this kind of an entry-exit point that this is ME1 and this was in ME2
and you know that ME1, the route from every ME1 to ME2 uses this E1-E2. So what
you will do is you will basically bubble up the amount of time for this route by 5
seconds. So what we are essentially saying is as then when you get traffic
data you basically update the ETA on a particular road. Then update the ETA on
all the calculated routes that this road is a part of.
And update and then basically that becomes at a segment level. And then do the same
thing recursively for all the segments that are a part of a mega segment.
So basically what you are doing is you're bubbling of all the calculated values
and then updating whole of the graph. Now these things are not happening
at once not all the signals are coming up at one, right. So as in when something
changes you bubble up till the level where it goes and then stop. So let's say this
road was not a part of this ME1 ME2 for example, then it will stop at the
segment level, right. But if it is a part of a mega segment road also, then it will
bubble up in the mega segment level. Now, other than just traffic and weather,
there's also one very important factor that you can use. So you can also use
historical ETAs to come up with a real or a predicted ETA for a particular Road.
And this historical ETA is basically calculated in a way that you
basically look at the day of week and the hour of day so let's say Monday, 5 p.m. this road takes 20 seconds to cover, but on Sundays 5 p.m. is this road
takes just 10 seconds to cover so something of that sort is what you can cache
at a level of a day of week and hour of day. And then use that historical data to
infer. So let's say if you do not have traffic information also, then you can use this
kind of an information to somehow come up with the predicted ETA.
Now coming back to the segment, due to some activities within the segment so let's
just say there are a lot of roads on the segment. There is there are these two
exit points and there are these points which have some roads now let's say
we've calculated that the ETA of fastest way to go from point
SE1 to SE2, involves 500 units of time. let's say 500 seconds, okay. And it uses
the route SE1 to A to B to C to SE2, okay. Now let's just say that there's a
traffic increase on A to B. Now we could identify it by a lot of attributes. Let's
just say people moving between A to B their average time increases right.
Or we get a signal saying you know the traffic is increasing significantly. For
whatever reason let's say we increase the time of
basically the ETA for going from point A to point B. So it would impact the ETA from
SE11 to SE2. Now there is a limit to which it can bubble up right so
let's say it increases from 500 to let's say 550 due to some increase in A to B
so all that is okay. But let's just say that we have real data of users, and for
some reason it is taking a lot of time for some people but we put to go from
point A to point B and let's just say this increases to let's say 850. Now a
jump from 500 units of time to 850 units of time is a very big jump. It is
having a.. roughly a 70% right. So now it is possible that the
fastest route from SE 1 to SE2 does not include this route ABC! It could be some
other route. So what we will do is if ETA increases or decreases, generally in case of increase only we'll do this. if ETA increases by greater than some
percentage. It's a configurable amount. Let's just say we have it set that if
the ETA increases by 30% then we recalculate things within that segment.
Because all the updates that you are getting are against a
segment only. So whenever a particular road's time increases you can
calculate everything within that segment, right. Which means recalculating paths from SE1 to SE2. Let's just say, that we figured out that
now the new shortest path is not this path and it is basically the pass from
SE1 to A to H to G to F to E and to SE2. So, this basically becomes your new shortest
path, right. Now if it is the shortest path, then we need to bubble up that
information, right. First of all we need to say that whoever was traveling from
SE1 to SE2, now needs to follow a new path right which is a path from
SE1-A- H - G - F - E - SE2, right. This is one part of the things. But what if there was
a mega segment over here which encompasses a lot of segments, whose exit
points were also including this particular path. This is let us say ME1
and let's say ME2. Now if the exit point path of this
Mega Segment also includes this part then even that mega segments path would
change so the part where they use ABC now that would get converted into this,
right. So these are the things that you'll have to do each time a weight changes.
so when the increases beyond the threshold then you have to do. So let's
just say increase happen from 500 to 510 then all of this calculation is probably
not even worth it. Because the best you can get is probably somewhere between
500 to 510. Now let's say 10 seconds would not be too much of an enhancement
right. But if it is such a big jump from 500 to 850 for example then you might as
well recalculate everything within the segment and then bubble up whatever is
required. Now you'll not just calculate with respect to exit points, you'll also
calculate the shortest path to reach from let's say SE1 to A, or SE1 to B.
All of those will also be calculated but for representation this was a good
enough way to explain you the concept. Now let's look at the architecture of
the whole system. So we will do it in two parts: First we'll look at the flow wherein all users are connected to the system
wherein we are capturing their location information from all the users even if
they are not using our map service. This is basically for improving our map
service altogether and a bit of user profiling. In the next section we'll look at
how does the actual navigation flow works for the user who want to find the
shortest route between two points and what are the systems required for that.
And at the end we'll look at some of the analytics. With that let's get started.
A bit of a convention to start with: Things in green are basically user devices
could be mostly these will be mobile phones, could be web browsers as well.
Things in black are load balancers plus reverse proxies plus an authentication
authorization layer in between which will authenticate all the external requests coming to the system.
Things in blue are the things that we have built on our own. It could be web services, Kafka
consumers or anything of that sort. Things in red are either some infrastructure
component that we've used or some databases or some clusters like Kafka, Hadoop and all of that, cool. So let's look at how the user flow begins.
The very first interaction with the user is when they when they have the app
installed on their phone, with their location services turn on, so we get
regular pings from a user's device every few seconds. Now if the user is
stationary, the device will have the logic to not send the location ping
every five seconds and maybe send it every five minutes or ten minutes or
something of that sort, because that will reduce the load on our system if the
user is anyway at the same point + Better battery life. But while the user is in transit, we will
increase the frequency, so as to make our data more accurate.
This talks to.. this basically keeps the persistent connection with the
device. The reason for a persistent connection is, so that we don't have to
create a new connection everytime. Also this would be generally a Websocket connection,
because sometimes we might need to send some information on to the user devices as well.
So this WebSocket handler is basically the service that talks to all
the user devices. Now there would normally be thousands of such WebSocket
handlers for talking to all the users that are currently online. So we need
somebody who can manage the fact that which handler machine is talking to
which user. So then comes something called as a Web Socket Manager.
It basically keeps a track of which machine(read user) is connected to which WebSocket handler,
so which user device is basically connected to which machine of
this WebSocket Handler Service. It basically keeps that information in a
Redis. If let's say it lost that information is lost we can kind of pull
that information again from the servers. So we don't need to kind of store that
information in a persistent Data Store. The next thing what happens is, as in when
users are sending their locations the frequency of the location pings is
handled by the device and then the device location comes to us
basically coming at the Location Service. Now Location Service is basically a
repository of all the location related information . It basically has some
endpoints through which you can ingest some users information, something like a
user ID with the timestamp with a particular Lat/Long. That kind of
a structure. It puts all of that information into a Cassandra as a
permanent data source to keep a track of the fact that which user was at what
location at what point in time. Remember this is not just for users who are using
our app right now for navigation, but for all the users in the world. How this
data would help us we'll come to in a while. Now, as and when it's getting location
pings, it is also putting all of those pings into a Kafka.
All the location pings that are going into this Kafka, are basically
read by this Spark Streaming Consumer. This does a lot of calculations,
some of them are here and some of them we look at in the later sections.
First of all what it does is, if let's say a lot of users are traveling at a place
where.. which we do not identify, okay. But their movement pattern tells
us it looks like a road. So this basically is a job which would be
a Streaming Job which would look at last ten minutes of data and see how the
users are moving and basically it'll be used to add new roads into our system.
Now as and when a new road is added each time a new road is added that would
basically impact the particular Segment within which the roads are added and
then basis that all the Segment related information that we calculated
earlier that we talked about earlier that would be recalculated. So that might impact
a lot of segments and Mega Segments recursively if that's a very critical new road that we've found. The next thing is
basically an average speed job. What that does is, it basically looks at again if
we look at within a segment a lot of people moving from point A to point B, it
tries to figure out what is the average speed that these users have over let's
say last fifteen twenty minutes and use that information to as a proxy for a
real-time information and then suggest that and basically it will then update the weights of the graph that we talked
about earlier. Again that would bubble up to various Segments and Mega
Segments if that's a part of a critical road. Now how would that bubble of
process happen? - So this Spark Streaming Job, individual jobs would actually write
back things into Kafka. So let's say if a new road is identified, it would write
that to a separate topic saying I've identified a new road which
connects point X to point Y. Now there will be a map update service which
listens to that particular topic and it updates it in a Data Store. It updates it
in a graphs Cassandra, which is managed by this Graph Processing
Service, so each time a new road is found, Map Update Service would invoke Graph
Processing Service to tell that I have found a new road just store that in your
Datastore which sits on top of a Cassandra. Now what this service is, we'll look
at in the next section in more detail. Now, each time average speed job finds out
there is some change that has happened it would again put an event into Kafka
in a separate topic now and there'll be something called as a Traffic Update
Service that listens to this topic which would update the traffic related
information again into the same Cassandra through Graph Processing Service.
There is something called as a Hotspot Identifier. So let's just say
there's a particular locality on which there is some average number of people
per given area kind of a metric that we have. Now let's have suddenly a lot of
people start gathering in that area it gives us a signal that there is some
activity happening at that point. It could be that there is some social
event, some sports thing happening or but something is happening there so that
could be able to identify hotspots within the graph. Because eventually once
we identify that hotspot we'll know that after probably a while, there will be a
lot of traffic in that area as well right. So that could help us in certain
ways. Now for certain things Spark Streaming would itself
insert a lot of information and put out events but in general it will dump all
of that data into Hadoop cluster, which has location pings of all the users
across a lot of time. Now we could do some ML Jobs onto it which
classify these certain other things. So let's say if you've identified a new
road but we do not know what kind of a road that is. If it's a one-way, if it's a
two-way Road, if it's a single lane road or maybe a six-lane Road. So all of those things would be identified by this Road Classifier and this particular job could now put that event into that road topic and Map Update Service could now store that additional information saying now that I have not just identified that
road but now I also know that this is a probably a six-lane Road or something of
that sort There could be something called as a Vehicle Identifier. While you are getting location pings, if you
start getting those pings at a very high frequency let's say every one
second if you are getting that you can input a lot of information about the
vehicle in which the person is traveling. So let's just say that the traffic is
going normal at certain pace but one particular person is stopping every few
kilometres let's say, okay. Now what that could mean that could mean that either
there's a red light or there's a traffic jam there, possibly. But we know what are
the junctions you know where the red lights can be we know how the
traffic jam are because we know the data for the user as well. Now if it's not
any of these two criteria then that means that the person is traveling in a
public transport something like a bus and then the bus is stopping at each bus
stop, all right. Other kind of things that we can infer is if let's say the ride is
bumpy or if the person is going left and right here and there very frequently or
having a very fast acceleration and very fast breaking it's probably a two wheeler.
if not in all other scenarios if it's a smooth enough right stable enough
acceleration going straight in one road it is very likely a four-wheeler. Now we
do tell information to Google specifically that we are actually
traveling in a two wheeler or four wheeler while we select a map but if
let's say that option is not available then this kind of data would be good
enough to infer which kind of vehicle a person is traveling in, which will help
us in a lot of other attributes. So these individual jobs what all they identify
they could put that into back into the same Kafka in probably a separate topic for each job and then those information could be
analysed even further. Now let's look at the user journey when they want to
actually get the navigation from point A to point B. So normally what people do is
they search for a particular location which then gets converted into a
particular lat/long right. So all of those is being done by Area Search
Service. This basically does two kind of things. One is, it has some areas within
Elastic Search on which it provides fuzzy searching and once the person has search
for a particular area or locality or location anything. It then
gets converted into a lat/long. So basically it stores the lat/long along
with the place name, description all of that, in a document. The other thing is it
tries to dynamically figure out: Given an address kind of a thing which lat/long
that address points to. So it does that address resolution into a lat/long as well.
Now let's say... so post the response from this user will have a start point
and end point as a latitude longitude both of them and then they would want to
request the path, okay. First let's quickly go over what is this Navigation
Tracking Service. So while the person is actually started the navigation and
they're going towards the destination all of their location coordinates will
be tracked as part of Navigation Tracking Service. This does two main things:
1) If the user is deviating from the route that we suggested, we will kind of inform
the app back and then that will probably show a pop-up kind of a thing, saying that
you are probably going wrong, maybe you want to course-correct to the right path.
2) It will also store all the data so it will push all of the data
into Kafka, while the person is traveling then that data could be used for later
analysis saying, at this point in time a person searched for a route from point A
to point B, and this was the route that we recommended. It could be used for
figuring out how good the recommendation of the path is. That being said, let's
jump to the main piece which actually figures out how to connect point A to
point B, okay. So all of those requests are being handled by this Map Service.
This Map Service over here is basically an interface service which provides
multiple interfaces for people to request the directions from some point
to some point. One of the interface is given to the user devices. A similar
interface could be given out to companies where in all the rate-limiting
and their throughput calculation against their account information is being
calculated and stored, okay. It's not an intelligent service it just
forwards the request to something called as a Graph Processing
Service. Graph Processing Service basically does a lot of things.
First of all it queries Segment Service which sits on top of its own Database of
Cassandra, in which it stores all the segments and their corner coordinates
along with a lot of information of those segments. So let's see if they if the
Graph Processing Service wants to figure out that what are the segment's for the
start point and the end point, it will get that information on the
Segment Service. Now if it so happens that both the points are within the same
segment then it's a short duration ride. Then the Graph Processing Service might choose to
do a couple of things it might look up that, Do have this
data already cached? if yes, it will directly return to the Map Service saying there is a response. If not, it'll then decide what do I do next?
It can now if it is the same segment it can probably say that I will run a
proper Dijkstra's algorithm and then try to figure out the shortest path between
the two points. It can do that and then return the response. Alternatively, if
it's in different segments then it will try to fan out into the whole basically
it will try to create a pick the sub graph of the main whole world's graph
that we want to look up as part of the Dijkstra and run it, okay. Now for doing
that it will look up on a lot of things. First of all it will look up for all the
roads within those segments, the entry-exit points of the segments,
into its Cassandra. It will also have live traffic information which would
have updated the ETAs into the graph again from the same Cassandra. Now it would have also got some input from something called as a Third Party Data Manager. Now it doesn't query Third Party Data Manager at runtime. Third Party Data Manager in fact, pushes data into Graph Service which then
impacts the live traffic information so let's say if it says that there is a
huge amount of traffic at certain point it'll update that. Let's say if it says
that there is a massive kind of a rain happening somewhere, it will update the
live traffic information thing there is some rain and that would probably cause some delays and the average speed would slow down and ETA would increase,
something of that sort. Now using all of that information it basically creates
the whole graph that we looked at in the previous sections and then it either
looks up in the cache and returns the result or it might run the Dijkstra's Algorithm or some Algorithm to basically figure out the shortest path between two
points and then return the result. let's say if it doesn't have any traffic
information, any ETA information it might also query Historical Data Service to find out at this point in time how much ETA can expect from point A to point B. if it doesn't have that information for some of the points. Now Historical Data Service sits on top of its own Cassandra which basically stores the information of the form that at some day, day of the week like Sunday, Monday, Tuesday in some hour, let's say 4 PM, 5 PM, something of that sort, from point A to point B, how much
was the average speed of people normally and how much ETA did it take. So all of that kind of information would be stored in Historical Data Service. Bases all of that, Graph Processing Service will return back the response to Map Service
and then to the user going by the exact same set of logic that we looked at in
the previous sections. Now all of this is done a lot of events have gone
into Kafka. One of the common events was that by the Area Search Service which we
didn't go over. So each time a search is happening the service will put an event
into Kafka. Now what that would do is it will basically give us a list of areas
that are being searched most often. So we can do some optimizations for them.
Another thing would happen is, so not we can do a lot
of analytic on top of this data okay that is coming into Kafka. One of the
very first thing we need to do is to figure out that out of all the third
party that we are integrated with which of them is actually giving right
information and which of them is actually given the wrong information. How
do we do that? So let's say some third party gave us some
information saying from point A to point B, there is a lot of traffic, and
ETAs would increase. But our data if it says that ETAs have not been impacted at
all, that means that particular information was incorrect, right. Now if
that happens from the same Third Party a lot of times, then we can safely say
that, that third party has a wrong information or it gives us wrong information. right. Now this Third Party Data Manager, abstracts out on a lot of third party companies, so we could be pulling data from a lot of companies all of that is abstracted under this Third Party Data Manager but the reporting
would be done at an individual organization level. That being said, there
are a lot of other kinds of analytics that we might want to do. First of all we
might want to identify what is the road that a particular person is on, right? so
as part of navigation you want to probably have a audio kind of a thing
saying turn right in ninety meters to get on Mahatma Gandhi Road,or something of
that sort, right. All of that inferences could be done by the Spark Streaming
saying where exactly I am in how much time am I about to reach a
junction and what is the road name on which I will get to next. So all of that
could be done by this. There are a lot of other analytics that we could also do on
top of this data. Let us look at it next. So out of all the events that are being
put into this Kafka, there is a lot of analytics that we can do and we should
do. So one of the very important things to analyze is how accurate our ETA
predictions are? So let's just say we predicted that it will take 40 minutes
to cover a distance from point A to point B and if it takes something around
38-39 minutes then that's fairly accurate. But if in real world it takes somewhere
around 20 minutes then that's a fairly bad prediction. So we need to have this
data on how accurate our predictions are so that we can figure out that we need
to invest more time into you know upgrading that algorithm that comes up
with the ETAs. Along with that it will also give us some information about
which of the routes are the ones that we are recommending to people, but people
are not taking. Maybe there is something wrong with the routes that exist in our
database, right. So all of those things could also be inferred. Some common things
that we can infer is what are some common hotspots in the city that people
gather at. These could be some social gathering places or things of that sort.
So that will kind of give us some points of interest that we can build over time
using this data to start with. Other than that some obvious things that we can also
figure out is, what are the home locations and work locations of some of
the people. We could also infer user profile data. So for example if a person
is going to a lot of pubs for example then they are more of a social kind of a
person. If a person is traveling outside the city very frequently on
weekends, the person likes travelling. So things like that can also be inferred
basis just a location data. Coming to the last thing, now this normally wouldn't be
a part of a design interview but there's something you should be aware of because
this is an important thing that companies like Google Maps have to take
care of. So how do you handle disputed areas? So while in Google Maps there is a
clear-cut boundary of states and countries and all of that but if there
is a disputed region how does Google Maps decide where to make the boundary of the
country or state right. So a classic example of this would be a dispute
between the countries of India, Pakistan and China in the state of Jammu and
Kashmir. So India claims that whole of the land is under their territory. China
claims that some of the parts of that state belongs to China and Pakistan
claims that some of the parts of that state belongs to Pakistan. So now how
does Google decide or any such mapping provider decides, that how where do they
define the country boundaries, right. Now this becomes very tricky for Google
because they cannot take anybody's side and whichever decision they make they
are going to kind of piss off some of the countries. Plus that's even worse
in this scenario because these three countries combined together have more
than one third of the world's population. So that's a very rich source of revenue
for Google. So how can you handle? - so what Google does is something very smart and
also very tricky. So what they do is, based on the country where you are coming from
they'll show you a different country boundary. So for people who are coming
from India, to all of those people they show that the whole part belongs to
India. Now to the people of Pakistan they show that the part that they are
claiming belongs to Pakistan and the parts that are disputed between India
and China are shown as the dotted line. Similarly for people coming from China
they show the part that China claims is theirs they show under China's
territory and remaining disputed area between India and Pakistan is shown as a
dotted line with no country boundary specified. So this is something if if you
come across this kind of the thing in an interview could try to replicate but
keep this out of the scope of the interview at least, but still something
good to know. So yeah I think this is it for Google Maps kind of a system.
