Bird
Raised Fist0

Design Google Maps - Road Graph, Routing Algorithm, ETA Computation

HLDhardInterview freq: high
Choose your preparation mode4 modes available
ArchitectureTraceChallenge
🏗️
Design Google Maps - Road Graph, Routing Algorithm, ETA Computation
High-scale, low-latency routing and ETA computation on a global road graph
hardLocation and Mapping SystemsFreq: high
Prerequisites:System Design FundamentalsCAP TheoremGraph AlgorithmsDistributed SystemsGeospatial Data Processing
⚙️
Functional Requirements
  • Store and update a global road graph with nodes (intersections) and edges (road segments)
  • Compute optimal routes between two points using shortest path algorithms considering real-time traffic
  • Provide ETA (Estimated Time of Arrival) computations based on route and live traffic data
  • Support multi-modal routing (driving, walking, cycling) with different constraints
  • Allow incremental updates to road graph and traffic data with minimal downtime
  • Expose APIs for route queries and ETA retrieval with low latency
📊
Non-Functional Requirements
  • Support 2 billion daily active users globally
  • Handle peak write throughput of 925K updates/sec (road graph + traffic updates)
  • Provide 100ms P99 latency for route and ETA queries
  • Ensure 99.99% availability with geo-redundancy
  • Scale to petabytes of geospatial data with retention of 1 year for historical traffic
❓
Clarifying Questions to Ask
  • What is the expected frequency and size of road graph updates versus traffic updates?
  • Are routing queries expected to be read-heavy compared to writes? What is the read/write ratio?
  • What is the geographic scope? Global or limited regions initially?
  • How accurate and fresh must the traffic data be for ETA computations?
  • Should the system support historical route and traffic data queries?
  • What are the latency SLAs for route computation and ETA response?
Out of Scope
✗ Detailed UI/UX design of Google Maps client apps
✗ Offline map storage and routing without network connectivity
✗ Integration with third-party map providers or POI databases
✗ Real-time incident detection and alerting systems
📌
Assumptions
  • 2 billion DAU globally
  • Each user generates 40 route/ETA queries per day on average
  • Average message size for updates (road graph or traffic) is 100 bytes
  • Peak write load is 10% of daily writes concentrated in rush hours
⚡
QPS Calculation
write qps2B users × 40 msgs/user/day ÷ 86400 sec ≈ 925,926 writes/sec
peak write qps925,926 × 10% peak factor ≈ 92,593 writes/sec
read qpsAssuming 10× read-to-write ratio, read_qps ≈ 9,259,260 reads/sec
💾
Storage Estimate
daily storage925,926 writes/sec × 100 bytes × 86400 sec ≈ 8 TB/day
retention days365
total storage8 TB/day × 365 days ≈ 2.92 PB
with replication2.92 PB × 3 replicas ≈ 8.76 PB
🖥️
Server Estimate
graph storage nodesAssuming 1 TB SSD per node, 3 PB / 1 TB ≈ 3000 nodes
routing compute nodesTo serve 9M QPS with 100ms latency, estimate 1000 nodes with GPUs/CPUs optimized for graph traversal
🏗️
Architecture Diagram
Architecture Diagram
          +----------------+
          |  Client Apps   |
          +-------+--------+
                  | Route/ETA API Calls
                  v
          +-------+--------+
          |  API Gateway   |
          +-------+--------+
                  |
        +---------+----------+
        |                    |
 +------+-----+        +-----+-------+
 | Routing Svc|        | Traffic Svc |
 +------+-----+        +-----+-------+
        |                    |
        v                    v
 +------+--------------------+-------+
 | Road Graph Storage (Cassandra)    |
 +------+--------------------+-------+
        |                    |
 +------+-----+        +-----+-------+
 | Kafka Topics|        | Redis Cache |
 +------------+        +-------------+
        |                    |
 +------+--------------------+-------+
 | Batch ETL & Graph Updater (Spark) |
 +-----------------------------------+
🧩
Components
API Gateway
Handles client requests for routing and ETA, load balances to backend services
Why thisEnvoy proxy provides high throughput, low latency, and supports global load balancing with service mesh integration
Why notNginx lacks native service mesh and dynamic routing features needed for global scale and multi-region failover
Routing Service
Executes shortest path algorithms (e.g., A*, contraction hierarchies) on road graph to compute routes
Why thisCustom C++ microservice optimized for low-latency graph traversal with precomputed indexes for fast queries
Why notUsing general-purpose graph DB like Neo4j is too slow for 100ms P99 latency at 9M QPS
Traffic Service
Ingests real-time traffic updates, adjusts edge weights dynamically for routing and ETA accuracy
Why thisKafka streams with Apache Flink for real-time processing and stateful computations on traffic data
Why notBatch ETL only would cause stale traffic data, violating 100ms latency and freshness requirements
Road Graph Storage
Stores global road graph data with partitioning by geography and indexes for fast access
Why thisApache Cassandra provides linear write scalability, geo-replication, and tunable consistency for distributed graph storage
Why notPostgreSQL with PostGIS cannot scale writes to 925K/sec and requires complex manual sharding
Redis Cache
Caches popular routes and ETA results to reduce load on routing service and improve latency
Why thisRedis TTL natively expires stale cache entries without cron jobs, supports sub-millisecond lookups
Why notMemcached lacks persistence and advanced eviction policies needed for complex geospatial caching
Kafka Topics
Decouples ingestion of road graph and traffic updates, enables asynchronous processing and replay
Why thisKafka supports high throughput, partitioning by region, and exactly-once semantics with Kafka Streams
Why notRabbitMQ does not scale as well for high-throughput partitioned streams and lacks strong ordering guarantees
Batch ETL & Graph Updater
Processes raw map data and incremental updates to maintain and optimize road graph indexes
Why thisApache Spark supports distributed batch processing and graph analytics at petabyte scale
Why notHadoop MapReduce has higher latency and less flexible APIs for iterative graph computations

Practice

(1/5)
1. A notification system must handle 1 million notification writes per second and fan out to millions of devices asynchronously. Which component best decouples the write load from delivery workers to ensure durability and scalability?
easy
A. Use a simple HTTP REST API to synchronously send notifications to all devices
B. Use a relational database with sharded tables to store notifications and poll for delivery
C. Use an in-memory cache like Redis to store notifications and push directly to devices
D. Use a distributed message queue like Kafka partitioned by user ID for ordered, durable fan-out

Solution

  1. Step 1: Identify the role of the message queue

    Kafka provides durable, partitioned logs that decouple producers from consumers, enabling high write throughput and ordered delivery per user.

  2. Step 2: Evaluate other options

    Relational DB polling (A) can't handle 1M writes/sec efficiently; Redis (C) lacks durability and persistence guarantees; synchronous HTTP (D) blocks on delivery and doesn't scale.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Kafka partitions by user ID -> durable, ordered fan-out [check]
Hint: Kafka partitions decouple writes from delivery at scale [check]
Common Mistakes:
2. In the typeahead system request flow, at step 4 the Ranking Service receives candidate suggestions from the Trie Cache. What does the Ranking Service do if the personalization data for the user is missing at this step?
easy
A. It returns an empty suggestion list immediately to avoid stale results
B. It blocks the request until personalization data is fetched synchronously
C. It falls back to global popularity-based ranking without personalization
D. It queries the Trie Cache again with a different prefix to compensate

Solution

  1. Step 1: Trace Ranking Service behavior at step 4

    Ranking Service combines candidate suggestions with personalization data; if missing, it must still return relevant results.

  2. Step 2: Evaluate fallback strategies

    Blocking for personalization data (C) causes latency; empty results (A) degrade UX; querying Trie again (D) is unrelated. Falling back to global popularity ranking ensures responsiveness.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Ranking Service fallback -> global popularity ranking [check]
Hint: Missing personalization -> fallback to global popularity ranking [check]
Common Mistakes:
3. A system must efficiently handle millions of concurrent calendar availability updates from hosts worldwide, ensuring low latency and eventual consistency. Which component is best suited to buffer and process these updates asynchronously?
easy
A. Use a relational database with strong ACID transactions for immediate consistency
B. Use a cache like Redis with TTL to store availability states temporarily
C. Use direct synchronous API calls to update availability in the main database
D. Use a distributed message queue like Kafka to decouple update ingestion from processing

Solution

  1. Step 1: Identify the need for asynchronous buffering

    Millions of concurrent updates require decoupling ingestion from processing to avoid bottlenecks.

  2. Step 2: Evaluate component suitability

    Relational DB (A) causes high contention and latency; Redis (C) is volatile and not durable; synchronous API calls (D) block and reduce throughput. Kafka (B) provides durable, ordered, and scalable buffering.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Kafka buffers high-throughput writes asynchronously with durability [check]
Hint: Buffer high-write updates asynchronously with durable queues [check]
Common Mistakes:
4. In a system where a user requests access to a protected resource, at step 4 the Authorization Service checks the user's access token. What happens if the token is expired at this step?
easy
A. The Authorization Service forwards the request to the Resource Server without validation
B. The Authorization Service grants access but logs a warning for token expiry
C. The Authorization Service refreshes the token automatically and proceeds
D. The Authorization Service rejects the request and returns an HTTP 401 Unauthorized error

Solution

  1. Step 1: Understand Authorization Service behavior at token validation

    The service validates token expiry and rejects expired tokens.

  2. Step 2: Eliminate incorrect behaviors

    Granting access with expired token violates security; automatic refresh is done by Authentication Service, not Authorization; forwarding without validation breaks security.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Expired tokens cause 401 Unauthorized rejection [check]
Hint: Expired token -> Authorization rejects with 401 Unauthorized [check]
Common Mistakes:
5. If the Bloom filter component is removed from a Cassandra-like system, what exact failure occurs during a read request for a non-existent key?
medium
A. The system returns stale data from cache without checking disk
B. Every read request for a non-existent key triggers a costly disk lookup, increasing latency and load
C. Writes block until the Bloom filter is rebuilt, causing backpressure
D. The system incorrectly returns key-not-found errors for existing keys due to missing filters

Solution

  1. Step 1: Understand Bloom filter role in reads

    Bloom filters prevent unnecessary disk reads for non-existent keys but do not affect correctness of existing keys.

  2. Step 2: Trace failure without Bloom filters

    Without Bloom filters, reads for non-existent keys cause disk lookups, increasing latency but do not cause incorrect key-not-found errors for existing keys; however, missing Bloom filters can cause stale data to be returned if caching is mismanaged.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Removing Bloom filters risks incorrect key-not-found errors due to stale cache [check]
Hint: No Bloom filter -> stale cache causes wrong misses [check]
Common Mistakes:
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard