System requirements

Functional:

• Users can specify a starting point and a destination by typing addresses and ask for the shortest route and estimated time of arrival.
• The system provides both a textual and graphical representation of the shortest route in terms of time.
• The system provides the estimated amount of time required to take that path.

Non-Functional:

• Low latency.
• Scalability.
• Availability.

Capacity estimation

User Traffic

• Peak Load: 10,000 Requests Per Second (RPS)
• With Overhead/Headroom: 12,000 RPS

2. Load Balancer (LB1 & LB2)

• Required Throughput: 12,000 RPS
• Instance Count: 3–6 (each handles ~2,000–5,000 RPS)
• Redundancy: Yes (at least 2 AZs)

3. API Gateway

• Peak Load: 12,000 RPS
• Instance Count: 6–8 (based on 2,000 RPS per instance)
• Key Functions: Auth, rate limiting, logging

4. Routing Service

• Handles: 12,000 RPS
  • Cache Hits: ~9,600 RPS (80%)
  • DB Accesses: ~2,400 RPS (20%)
• Instance Count: 8–10 (based on 1,500 RPS per instance)

5. Cache (e.g., Redis)

• RPS: 9,600 (reads)
• Memory Need: ~550 MB (based on 1 min TTL)
• Cluster Setup: 3–5 shards + replicas
• Latency Target: ≤2 ms

6. Database

• Read Load: 2,400 RPS
  • Throughput: ~4.8 MB/sec
  • Read Replicas: 5 (500 RPS per replica)
• Write Load: Depends on use case
  • Primary DB Instances: 1–2

API design

GET /route {

start_point

end_point

} - returns list os roads and estimates time to arrival.

Database design

We can represent map as graph , where nodes - road intersections and edges - roads with metrics (distance, speed limits, traffic data). Lets split graph on grid with layers, where layers represent : 1) local, small roads, 2 larger streets typically within a city, and 3 highways.

nodes table {

node_id,

lon,

lat

}

edges_table {

edge_id,

source_node_id,

target_node_id,

length_m,

speed_limit_kph,

road_class,

is_one_way,

traffic_factor,

last_updated_at

)

edge_profiles_table {

edge_id

car_cost

truck_cost

bike_cost

pedestrian_cost

}

High-level design

1. User

• Mobile App / Web Client
• Requests map data, directions, etc.

2. Load Balancer (Global)

• Geo-aware routing to nearest data center
• Uses DNS + edge routing ( Cloud CDN)

3. API Gateway

• Rate limiting, auth (OAuth2), request logging
• Parses endpoints like

4. Internal Load Balancer

• Routes requests to appropriate microservices

5. Routing Service

• Handles core logic for:
  • Pathfinding (A*, Dijkstra’s, Graph optimizations)
  • Real-time traffic adjustments
  • Toll roads, public transit, time windows

6. Cache Layer (e.g., Redis, Memcached)

• Stores frequently accessed paths, popular routes, and tiles
• Reduces latency and DB hits

7. Database Layer

• Road Network Graph DB: Used for route computation

Request flows

User enters origin and destination.

API Gateway routes request to Routing Service.

Routing Service checks Cache for existing route (origin + destination + time).

If cache hit → return cached path.

If miss:

• Pulls road graph from Road Network DB.
• Computes optimal route (A*/Dijkstra).

Response is cached and returned to the user.

Detailed component design

1. User

• Represents the client (browser/mobile app/IoT device).
• Sends HTTP(S) requests to interact with the backend system.

2. Load Balancer (LB) #1

• Purpose: Distributes incoming user traffic across multiple instances of the API Gateway.
• Type: Could be Layer 4 (TCP) or Layer 7 (HTTP/HTTPS) load balancer.
• Features:
  • SSL termination
  • Health checks
  • Rate limiting

3. API Gateway (API GW)

• Purpose: Acts as a single entry point for all API requests.
• Responsibilities:
  • Request routing
  • Authentication & Authorization (e.g., OAuth2, JWT)
  • Request transformation (e.g., header/body modification)
  • Logging and metrics
  • Rate limiting
• Examples: AWS API Gateway, Kong, Apigee, NGINX

4. Load Balancer (LB) #2

• Purpose: Distributes API requests to backend microservices (here, the Routing Service).
• Ensures horizontal scalability of the Routing Service layer.
• Could use round-robin, least connections, or custom logic.

5. Routing Service

• Purpose: Decides whether to serve data from Cache or fetch from Database.
• Typical Logic:
  • Check if data is in Cache
    • If hit, return data
    • If miss, query Database, cache the result, and return it
• Responsibilities:
  • Cache key generation
  • TTL (Time To Live) management
  • Request de-duplication
  • Observability/logging

6. Cache

• Type: In-memory key-value store (e.g., Redis, Memcached)
• Use Cases:
  • Frequently accessed data
  • Session storage
  • Rate limiting counters
• Considerations:
  • TTL management
  • Cache invalidation
  • Consistency model

7. Database

• Type: SQL (e.g., PostgreSQL, MySQL) or NoSQL (e.g., MongoDB, Cassandra)
• Responsibilities:
  • Persistent data storage
  • ACID compliance (for SQL DBs)
  • Handles complex queries and relationships

Trade offs/Tech choices

Trade offs between Dijkstra and A* algorithms.

Failure scenarios/bottlenecks

Try to discuss as many failure scenarios/bottlenecks as possible.

Future improvements

What are some future improvements you would make? How would you mitigate the failure scenario(s) you described above?