Bird
Raised Fist0

Design a Real-Time Location Tracking System - GPS, WebSocket, Geo-indexing

HLDhardInterview freq: medium
Choose your preparation mode4 modes available
ArchitectureTraceChallenge
🏗️
Design a Real-Time Location Tracking System - GPS, WebSocket, Geo-indexing
Real-time ingestion, processing, and querying of GPS location data at massive scale with low latency
hardLocation and Mapping SystemsFreq: medium
Prerequisites:HTTPTCP
⚙️
Functional Requirements
  • Ingest GPS location updates from 2 billion daily active users (DAU) devices in real-time.
  • Support bi-directional WebSocket connections to stream live location updates to subscribed clients with <100ms P99 latency.
  • Provide geo-spatial queries to find nearby users or objects within a radius or bounding box.
  • Store location history for at least 7 days for replay and analytics.
  • Support user presence and online/offline status updates.
  • Allow clients to subscribe/unsubscribe to location updates of specific users or geographies.
📊
Non-Functional Requirements
  • System must handle 2 billion DAU generating 40 location messages per day each.
  • End-to-end latency for location update delivery to clients must be under 100ms P99.
  • Availability SLA of 99.99% for ingestion and streaming APIs.
  • Data retention of 7 days with eventual archival to cold storage.
  • System must scale to 10x load without major redesign.
❓
Clarifying Questions to Ask
  • What is the expected peak concurrency of WebSocket connections?
  • Are location updates always from mobile devices or also from IoT devices?
  • What geo-spatial query types are required? Radius, polygon, nearest neighbor?
  • Is the system required to support offline buffering on devices?
  • What is the maximum acceptable staleness for location data in queries?
  • Should the system support multi-region deployment for geo-redundancy?
Out of Scope
✗ Detailed device-side GPS accuracy correction or sensor fusion.
✗ Long-term historical analytics beyond 7 days.
✗ User authentication and authorization mechanisms.
✗ Map rendering or routing algorithms.
📌
Assumptions
  • 2 billion DAU
  • 40 location messages per user per day
  • 100 bytes per location message (including metadata)
  • Peak write QPS is 5x average write QPS due to diurnal usage patterns
⚡
QPS Calculation
write qps2,000,000,000 × 40 / 86,400 ≈ 925,926 msg/sec
peak write qps925,926 × 5 = 4,629,630 msg/sec
read qpsAssuming 3 reads per write for subscriptions, 925,926 × 3 = 2,777,778 reads/sec
💾
Storage Estimate
daily storage925,926 msg/sec × 100 bytes × 86,400 sec ≈ 8 TB/day
7 day retention8 TB × 7 = 56 TB
with replication56 TB × 3 (replication factor) = 168 TB total storage
🖥️
Server Estimate
ingestion serversAssuming each server handles 50K writes/sec, need 4,629,630 / 50,000 ≈ 93 ingestion servers
streaming serversAssuming each WebSocket server handles 10K concurrent connections, with 100M concurrent connections, need 10,000 streaming servers
🏗️
Architecture Diagram
Architecture Diagram
          +----------------+
          |  GPS Devices   |
          +-------+--------+
                  |
                  | HTTP POST (location updates)
                  v
          +-------+--------+
          | Ingestion Layer|
          | (Nginx + Envoy)|
          +-------+--------+
                  |
                  | Kafka (partitioned by user_id)
                  v
          +-------+--------+
          |  Processing    |
          | (Flink + Kafka |
          | Streams)       |
          +-------+--------+
          /               \
         /                 \
        v                   v
 +------+-------+    +------+-------+
 | Geo-Indexed   |    | Time-Series  |
 | DB (Cassandra |    | DB (Cassandra|
 | + GeoMesa)    |    | + ScyllaDB)  |
 +------+-------+    +------+-------+
        |                   |
        |                   |
        v                   v
 +------+-------+    +--------------+
 | WebSocket    |    | REST API     |
 | Streaming   |    | Servers      |
 | (Netty +    |    | (SpringBoot) |
 | Redis PubSub)|    +--------------+
 +--------------+
🧩
Components
Ingestion Layer (Nginx + Envoy)
Receive GPS location updates over HTTP POST from billions of devices, perform rate limiting and TLS termination.
Why thisNginx + Envoy provide high throughput, TLS offloading, and HTTP/2 support with mature ecosystem and observability.
Why notDirect Kafka ingestion rejected due to lack of TLS termination and HTTP protocol support at scale.
Kafka Cluster
Durable, partitioned, ordered ingestion buffer for location updates, partitioned by user_id for write scalability.
Why thisKafka supports 10M+ writes/sec per cluster with partitioning, replication, and retention policies ideal for real-time streaming.
Why notRabbitMQ lacks horizontal partitioning and throughput at this scale; Kinesis is cost-prohibitive at billions of messages.
Stream Processing (Apache Flink + Kafka Streams)
Process and enrich location data streams, filter stale data, compute presence, and fan-out updates to downstream stores and WebSocket servers.
Why thisFlink provides exactly-once semantics, low latency, and stateful stream processing needed for real-time geo-indexing and presence.
Why notSpark Streaming has higher latency and batch micro-batching unsuitable for <100ms P99 latency.
Geo-Indexed DB (Cassandra + GeoMesa)
Store and index location points with geo-spatial queries support for radius and bounding box queries.
Why thisCassandra scales linearly with write throughput; GeoMesa adds geo-indexing on top enabling efficient spatial queries at scale.
Why notPostgreSQL with PostGIS cannot handle 925K writes/sec and 3M reads/sec at scale without complex sharding.
Time-Series DB (Cassandra + ScyllaDB)
Store time-series location history for 7-day retention with efficient range queries by user and time.
Why thisCassandra and ScyllaDB provide high write throughput, low latency reads, and TTL-based automatic data expiration.
Why notInfluxDB or TimescaleDB do not scale linearly to billions of writes per day and have higher operational complexity.
WebSocket Streaming Servers (Netty + Redis Pub/Sub)
Maintain persistent WebSocket connections to clients, push real-time location updates with sub-100ms latency.
Why thisNetty provides high concurrency and low latency TCP handling; Redis Pub/Sub enables efficient fan-out of updates to many connections.
Why notHTTP long polling or Server-Sent Events (SSE) cannot achieve the required latency and scale for billions of concurrent connections.

Practice

(1/5)
1. In the payment system's request flow, at Step 5 the Settlement Service receives a batch of transactions marked as 'authorized'. What does the Settlement Service do when it encounters a transaction flagged as 'already settled' during this step?
easy
A. It marks the transaction as failed and triggers a manual review
B. It retries settlement immediately to ensure idempotency
C. It skips the transaction and logs it as a duplicate to avoid double settlement
D. It forwards the transaction back to the Authorization Service for re-validation

Solution

  1. Step 1: Trace Settlement Service behavior at Step 5

    The Settlement Service must avoid double settlement by skipping transactions already marked as settled.

  2. Step 2: Evaluate other options

    Retrying settlement risks duplicate charges; marking as failed triggers unnecessary manual work; forwarding back to Authorization Service is redundant.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Settlement skips duplicates -> prevents double charges [check]
Hint: Settlement skips already settled transactions [check]
Common Mistakes:
2. A system must handle 1 million writes per second with flexible schema and eventual consistency. Which database technology best fits this requirement?
easy
A. Use a NoSQL document store with horizontal sharding
B. Use a traditional relational database with vertical scaling
C. Use an in-memory cache like Redis without persistence
D. Use a graph database optimized for complex joins

Solution

  1. Step 1: Identify write throughput and schema flexibility needs

    Relational DBs struggle with 1M writes/sec and rigid schemas; graph DBs optimize for relationships, not write scale.

  2. Step 2: Evaluate NoSQL document store capabilities

    NoSQL document stores support horizontal sharding and flexible schemas, enabling high write throughput with eventual consistency.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    NoSQL document stores scale horizontally for high writes [check]
Hint: High writes + flexible schema -> NoSQL document store [check]
Common Mistakes:
3. For minimizing end-to-end latency in converting RTMP streams to HLS, which architecture is better given mobile clients with limited HTTP/2 support?
medium
A. Use a CDN with HTTP/1.1 chunked transfer encoding to stream HLS segments progressively
B. Use gRPC streaming to push segments with multiplexed streams
C. Use WebSocket connections to push HLS segments directly to clients
D. Use HTTP/2 server push to deliver HLS segments immediately upon generation

Solution

  1. Step 1: Consider client compatibility

    Mobile clients often have limited or inconsistent HTTP/2 support, making HTTP/2 server push (A) and gRPC streaming (D) unreliable.

  2. Step 2: Evaluate streaming methods

    WebSocket (C) is not natively supported by HLS players and complicates caching/CDN usage. HTTP/1.1 chunked transfer encoding (B) allows progressive delivery compatible with most clients and CDNs.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    HTTP/1.1 chunked encoding streams HLS segments progressively and broadly supported [check]
Hint: Chunked HTTP/1.1 streams HLS segments; mobile supports it best [check]
Common Mistakes:
4. Without the message broker's offset commit mechanism, what exactly breaks in the delivery flow?
medium
A. Producers block indefinitely waiting for acknowledgments
B. Messages are lost silently because offsets are not persisted
C. Messages are duplicated indefinitely because consumers cannot track progress
D. Consumers receive messages out of order due to missing broker coordination

Solution

  1. Step 1: Role of offset commit in consumer progress tracking

    Offset commits mark messages as processed; without them, consumers reprocess the same messages repeatedly.

  2. Step 2: Consequence of missing offset commits

    Consumers cannot advance their read position, causing duplicate deliveries; messages are not lost or reordered inherently.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    No offset commit -> infinite duplicates, no progress [check]
Hint: No offset commit -> consumer reprocesses same messages repeatedly [OK]
Common Mistakes:
5. At 10x scale, which component in a saga-based event-driven system is most likely to fail first due to stateful bottlenecks, and why?
hard
A. The saga coordinator, because it maintains in-memory state per saga and cannot shard easily
B. The message broker, because partition count limits throughput and ordering guarantees
C. The database, because increased writes cause lock contention on outbox tables
D. The event relay service, because network bandwidth saturates before CPU

Solution

  1. Step 1: Identify stateful bottleneck

    The saga coordinator holds per-saga state in memory, limiting horizontal scaling and sharding.

  2. Step 2: Compare other components

    Message brokers scale with partitions; DB scales with sharding; relay is stateless and network-bound.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Saga coordinator's in-memory state limits scaling first [check]
Hint: Stateful saga coordinator limits scaling before stateless components [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