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

For each edge compute effective speed


effective speed  = x * real_time_speed  + (x-1) * historical_speed

    - x is the importance (from 0 to 1) for the traffic data
    - Real time speed is derived from tarffic data for that
    edge from redis
- Historical data is historical traffic data for that edge for the given time in history.

Compute time

time = distance / effective speed

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

Run A* algo along the time-weighted graph

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:

  edge A -> [userA, speed: 50], [userB, speed: 30]

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

	   if distance_along_route > step end location:
            trigger next update

- - 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

      if distance_along_route > threshold
          trigger reroute

- 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.

	    recive old time, new Time from traffic updated envt
        ETA_delta = new_time - old_time
        final eta += eta_delta

Scalability

Map Tiles: Served through global CDN with object storage as source of truth. CDN handles billions of read requests and reduces backend load.
GPS / Traffic Pipeline: Location updates are streamed through Kafka partitioned by geo-region. Map matching and Flink aggregation services scale horizontally. Redis is sharded by edgeId for traffic lookups.
Routing: Route services are stateless and horizontally scalable. Road graph data is replicated across regions, and popular routes can be cached.

Failure Handling

Kafka/Flink failure: Kafka replication prevents data loss. Flink checkpoints allow recovery. Traffic data can temporarily fall back to last known values.
Redis failure: Redis replication/failover is used. Losing navigation sessions is acceptable because sessions can be recreated from client GPS updates.
Service/Region failure: Services run across multiple instances and regions with load balancing. Routing can fall back to historical traffic if real-time traffic is unavailable.
GPS connectivity issues: Missing GPS updates are tolerated. Navigation sessions expire using TTL if no updates are received.

Consistency Tradeoffs

Traffic data: Eventual consistency is acceptable because traffic changes frequently. A slightly stale congestion value is better than slowing down routing.
Navigation sessions: Strong consistency is not required. Losing a temporary session is acceptable because it can be recreated from client state.
Road graph/map data: Requires stronger consistency because incorrect roads can create wrong routes. Updates are versioned and rolled out gradually.
Route caching: Cache popular routes with a short TTL. Since traffic changes, cached routes may become stale, so cache is only used as an optimization and routes are refreshed when traffic changes significantly.

Submissions

Displaying Solutions with Scores Ranging from 1 to 10

Submissions

Displaying Solutions with Scores Ranging from 1 to 10