Requirements

Functional Requirements:

• Display a map of the current viewport
• Given source and destination, calculate the fastest route
• Calculate ETA
• Provide turn-by-turn navigation when user starts a navigation
• Update the route and ETA when user deviates from their route

Non-Functional Requirements:

• Highly available ~99.9% uptime, map should always load
• Highly scalable - billions of map tile rquests, millions of route requests
• Low latency - <100ms map tile loading, <500ms routing
• Traffic updates - eventual consistency
• Map/routes should be accurate

Capacity Estimation

• 500M DAU
• 50M concurrent users

Map tile requests

• One screen map needs ~20 tiles
• 100 tile requests/sessions
• 500M sessions daily
• 50B map tile requests/daily
• ~500K QPS
• Peak - 5x -> 2.5M QPS

Route/Navigation requests

• 100M/day
• 1K QPS
• Peak - 5x -> 5K QPS

Traffic updates

• Millions of vehiles/users constantly sending gps update locations
• Huge streaming workload

API Design

GET /tiles/{zoom}/{x}/{y} - CDN cacheable

Response - {

tileId,

data, -> tile image or vector,

}

POST /route

req - {

src,

dest

}

res - {

id,

distance,

eta,

polyline,

steps[],

}

POST /navigation//start

req - {routeId}

POST /route/{id}/reroute -> same functionality as route but used when user deviates to reroutre from current route

POST /location -> gps updates

req - {

userId,

lat,

long,

speed

}

High-Level Design

API Gateway

Acts as the entry point for all client requests.

Responsibilities:

• Authentication (if required)
• Rate limiting
• Request routing

Load Balancer

Distributes traffic across multiple instances of all services to improve scalability and availability.

Route Service

Responsibilities

• Receives routing requests
• Normalizes src and dest locations to edgeIds using map matching services
• Generates a time-weighted graph from the both src and dest edgeIds
• Runs A* algo along the time weighed graph
• The A* algo results in an ETA, fastest route and step by step instructions
• Creates a new Navigation session in redis and a websocket between for the client for this route.

Location Service

Responsibilities

• Receives real time gps location raw updates
• Pushes the raw updates to kafka
• Doesn't handle the raw gps updates on its own as its heavy streaming workload

Map Matching service

Responsiblities

• Consumes the raw gps events from kafka
• Normalzies the lat/long to a edgeId from road graph
• Pushes the normalized gps event to kafka

Traffic aggregation Service

Responsibilites

• Consumes normalized gps eevents
• Uses Flink for stream processing
• Aggreates gps data to calculate traffic info such as congestion level, speed etc
• Every 10 sec flushes the traffic data into Redis

• Also flushes the traffic data into datawarehouse, which is used to transform/calculated into updating historic traffic data

Navigation Service

Responsibilites

• Also consumes normalized GPS events
• Uses it for user active navigation session
• Checks if user have active navigation session from Redis
• If active session found
  • Using gps location, finds current user location in the polyline data of route
  • Determines user current step in route
  • Updates navigation session to reflect the user progress.
  • If user deviates from route -> triggers reroute
  • Sends update if required for next step to client via websocket gateway

Kakfa

• GPS event message queue
• Gurantees at least once delivery
• Uses geoloaction as patition key

Redis

• Stores Traffic data and navigation session
• Traffic data TTL is ~1 day
• Navigation session TTL is 5 mins
  • Updated for every gps events consumed by navigation service and active session found
  • If no updates made in 5 min (app crahsed, user stopped navigation, user closed app) its cleared out

Road Graph DB

• stores road connections graph

Object storage

• Stored map tiles data

CDN

• caches map tiles data
• Uses global per region CDN, so client connects to the nearest CDN edge
• Fallbacks to object storage on cache miss

Database Design

We use hybrid approach, as we have various data points to take care of.

Road connections(Node, Egde) will be stored in a Graph DB

Node

id

lat

long

Edge

fromNode

toNode

distance

speedLimit

Route / Navigation session -> stored in redis as its temporary data, for historical analytics and stuff could be also persited in data lake/warehouse

id

src

dest

status

steps[]

Traffic Data

segmentId

congestion,

speed,

lastUpdated

Map tile -> stored in Object storage and cached in CDN

tileId,

data -> image or vector

Detailed Component Design

Now we will deep dive into the following topics

ETA Calculation

• Route service recives the request
• Route service makes use of - Map matching service to determine src and dest edge ids, Redis to get traffic info for along the route.

Generating Time-weighted graph

1. For each edge compute effective speed

1. Compute time

1. Take attributes such as Traffic lights, road type etc into accoutn and update time.
2. attach the time to the edge
3. Repeat this for each edge
4. Final result = time-weighted graph

Run A* algo along the time-weighted graph

1. This will result in:
   1. Fastest route
   2. ETA (sum of all time in all edges in the fastest route)
   3. Step-by-step instructions

• The ETA calculated is then stored in Navigation Session

Traffic Data Calculation

• Traffic data is calculated by GPS events streamed from client devices every few seconds
• Event transimmited has -> userId, speed, lat and long
• The event is sent to kafka as raw event
• Map matching service will consume it and normalize it ending with -> userId, speed, edgeId
• So now we have at Edge A, User B is going at Speed X
• All those events are streamed to kafka again as Normalized gps events
• Traffic aggrgation service will consume those events. It uses Flink as streaming service
• This service will aggreate data by edgeIds for eg:

• Using this aggregation, the service determines Traffic data, it checks the Edge info, like the speed limit, historical speed data for that edge and caulcautes Traffic congestion level and determines a current avg real speed. Avg Speed = sum of all speed / total user evetns at that edge.
• This aggreaged data is flushed to redis every 10 sec.
• Thus, we end up with traffic data in redis which is eventual consistency and is then later used for calculating ETA.

Rerouting User / Providing Step by Step instrucntion/ Updating ETA

• All of these is handled by navigation Service.

Rerouting User / Providing Step-by-Step Instruction:

• Navigation service will also consume normalized gps events
• IT will check if the user from the gps events has any active navigation session from redis
• If session found:
• Providing Step-by-Step Instruction:
  • It that determinses user current point in route using polyline
  • IT will update user progress -> distance along route
  • It will determine if user passed a step is now on next step.
    • Each step has a trigger location or step end locaiton

• • • Using this formula we check if user is on next step.
    • The client is notified of this update via websocket connection which was created when route as stored in redis
• Rerouting user:
  • Similar to above, we have theshold set to trigger retoute.
  • So after calcuating distance along route and checkign if user passed current step end locaiton, we have check for this

• • this means if user deviates, we trigger the reroute API, which will recaculate route form user current locaiton to route's destination. works just as saem as Route API.
• ETA updates:
  • While user is in navigation, we provide ETA updates when something changes along the route. like road blockage, , accident happen etc
  • This ETA update is actually triggered mainly by traffic info updates
  • So when a traffic updated it will also put out a TrafficUIpdated event to Kafka
  • This will be consumed by Navigation service
  • Navigation service checks all the user along the route, maybe we have a reverse indexing stored in redis, like Edge A has user A, userB and UserC in route, so it becomes faster to find all user in route for that edge.
  • Once we have all user, we find their session/route into from redis.
  • We will then only apply parital ETA update i.e. rateher than full ETA calcualtion we will only do update for the edge where traffic is updated.

Scalability:

• For traffic data - horizontal all services involved, partition kafka events by geo location
• ETA/route calculation - pure code logic so horizontal scale routing services