Bird
Raised Fist0

Yelp / Proximity Service - Geohash, Quadtree, Nearby Search

HLDhardInterview freq: medium
Choose your preparation mode4 modes available
🏗️
Yelp / Proximity Service - Geohash, Quadtree, Nearby Search
Design a scalable proximity search service using geohash and quadtree indexing for real-time nearby place queries
hardLocation and Mapping SystemsFreq: medium
Prerequisites:Inverted IndexElasticsearch
⚙️
Functional Requirements
  • Support querying nearby places (restaurants, shops, etc.) within a radius or bounding box
  • Index places using geospatial data structures (Geohash + Quadtree) for efficient spatial queries
  • Support real-time updates for place data (add, update, remove) with low latency
  • Provide ranked search results based on proximity and optional filters (category, rating)
  • Support pagination and sorting of nearby search results
  • Expose APIs for client apps to query nearby places with location and radius parameters
📊
Non-Functional Requirements
  • Handle 2 billion daily active users (DAU) with peak 925K writes/sec and 10M reads/sec
  • 99.99% availability SLA for search queries
  • P99 query latency under 100ms for nearby search
  • Data freshness within 1 minute for place updates
  • System must scale horizontally with minimal manual sharding
❓
Clarifying Questions to Ask
  • What is the expected average and peak query radius for nearby searches?
  • What is the update frequency and volume for place data (adds/updates/deletes)?
  • Are there any constraints on the geographic coverage (global, regional)?
  • What filters or ranking criteria besides proximity must be supported?
  • Is the system expected to support user-generated content like reviews or photos?
  • What is the expected consistency model for place data visibility after updates?
Out of Scope
✗ Detailed UI/UX design of the Yelp app
✗ User authentication and authorization
✗ Complex recommendation algorithms beyond proximity and simple filters
✗ Offline map rendering or navigation
📌
Assumptions
  • 2 billion DAU
  • Each user generates 40 location-based queries per day
  • Average place update size is 100 bytes
  • Retention period for place data is 30 days
⚡
QPS Calculation
write qps2B × 1 update per 10 users per day / 86400 ≈ 231K writes/sec
peak write qpsAssuming 4x peak factor → 231K × 4 = 924K writes/sec
read qps2B × 40 queries/day / 86400 ≈ 925K queries/sec average; peak 4x → 3.7M reads/sec
💾
Storage Estimate
daily storage231K writes/sec × 100 bytes × 86400 sec ≈ 2 TB/day
retention storage2 TB/day × 30 days = 60 TB
with replication60 TB × 3 replicas = 180 TB total storage
🖥️
Server Estimate
write nodesKafka clusters + ingestion nodes: 50 nodes (each handles ~20K writes/sec)
search nodesElasticsearch cluster: 200 nodes (each handles ~20K queries/sec with geo-indexing)
🏗️
Architecture Diagram
Architecture Diagram
Client Apps
    |
    v
API Gateway
    |
    v
Write Path: Ingestion Service --> Kafka (Partitioned by Geohash)
    |                                         |
    v                                         v
GeoIndexer Service ---------------------> Elasticsearch Cluster
    |                                         |
    v                                         v
Read Path: API Gateway <------------------ Elasticsearch Cluster
🧩
Components
API Gateway
Handles client requests, routes to write or read services, enforces rate limits
Why thisNginx + Envoy proxy provide high throughput, low latency routing with TLS termination
Why notDirect client-to-backend bypasses centralized control and complicates scaling and security
Kafka
Durable, partitioned write-ahead log for place updates, partitioned by geohash prefix
Why thisKafka supports high throughput (millions of writes/sec), partitioning by geohash enables locality and parallelism
Why notRabbitMQ lacks Kafka's throughput and partitioning scalability at 925K writes/sec
GeoIndexer Service
Consumes Kafka updates, converts place data into geohash and quadtree indexes, writes to Elasticsearch
Why thisCustom service allows flexible spatial indexing logic and batching for efficient ES writes
Why notDirect writes from ingestion to ES cause hot shards and inconsistent indexing
Elasticsearch Cluster
Stores inverted geospatial indexes using geohash and quadtree, supports fast nearby search queries
Why thisES supports geo_point and geo_shape types with optimized spatial queries and inverted indexes
Why notCassandra lacks native geospatial indexing and efficient radius queries
Client Apps
Mobile/web apps that send location queries and display nearby places
Why thisNative apps provide best user experience and leverage device GPS
Why notWeb-only clients limit offline capabilities and location accuracy
🔄
Data Flow
1
Client Apps → API Gateway
Send nearby search or place update request
Requests include user location, radius, or place data
2
API Gateway → Kafka
Place updates are published to Kafka topic partitioned by geohash prefix
Ensures locality and parallel processing
3
GeoIndexer Service → Kafka
Consume place update messages, build geohash/quadtree indexes
Batch updates for efficient ES writes
4
GeoIndexer Service → Elasticsearch Cluster
Write spatially indexed place documents to ES
ES shards partitioned by geohash prefix for query locality
5
Client Apps → API Gateway
Send nearby search query with location and radius
API Gateway routes to ES cluster
6
API Gateway → Elasticsearch Cluster
Execute geo-distance or bounding box query using geohash/quadtree indexes
ES returns ranked places by proximity and filters
7
API Gateway → Client Apps
Return paginated nearby places search results
Results include place metadata and distance

Practice

(1/5)
1. A public API needs to support multiple client versions simultaneously without breaking existing integrations. Which versioning strategy best isolates client requests to avoid accidental breaking changes?
easy
A. Use content negotiation with Accept header media types to specify version
B. Use a custom HTTP header like X-API-Version to specify the version
C. Embed the version number in the URL path, e.g., /v1/resource
D. Rely on query parameters like ?version=1 to indicate API version

Solution

  1. Step 1: Identify version isolation requirements

    Embedding version in the URL path clearly separates client requests by version, preventing accidental routing to incompatible handlers.
  2. Step 2: Evaluate alternatives

    Custom headers and content negotiation can be ignored or mishandled by intermediaries or caches, risking breaking changes. Query parameters are less explicit and can cause caching issues.
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    URL versioning cleanly isolates versions in routing paths [check]
Hint: URL path versioning isolates clients cleanly [check]
Common Mistakes:
2. A large-scale messaging platform needs to isolate failures to prevent cascading outages during regional network partitions. Which architectural component best limits the blast radius by decoupling service dependencies?
easy
A. Use synchronous REST calls between microservices with retries
B. Use direct TCP socket connections between services for low latency
C. Implement asynchronous message queues with backpressure and dead-letter queues
D. Rely on a single monolithic database to coordinate all service state

Solution

  1. Step 1: Identify failure isolation mechanism

    Asynchronous message queues decouple services, buffering requests and preventing direct cascading failures during outages.
  2. Step 2: Evaluate alternatives

    Synchronous REST calls (A) cause blocking and cascading failures; monolithic DB (C) is a single point of failure; direct TCP (D) lacks buffering and backpressure.
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    Async queues buffer and isolate failures, limiting blast radius [check]
Hint: Async queues buffer failures, blocking calls cascade [check]
Common Mistakes:
3. In the faceted search request flow, at Step 4 the Query Coordinator merges partial results from multiple shard nodes. What happens if one shard node responds with a partial result missing some facet counts due to a timeout?
easy
A. The Query Coordinator excludes the shard's data entirely from the final result
B. The Query Coordinator merges available partial results and marks missing facets as zero counts
C. The Query Coordinator returns an error to the user immediately
D. The Query Coordinator retries the shard query synchronously before merging

Solution

  1. Step 1: Understand Query Coordinator's merge logic

    The coordinator merges partial results from all shards; if a shard times out, its data is excluded to avoid blocking the entire query.
  2. Step 2: Eliminate other options

    Returning an error breaks availability; marking missing facets as zero is inaccurate; synchronous retries would increase latency.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Timeout shard data excluded -> partial but available results [check]
Hint: Timeout shards excluded to keep query latency low [check]
Common Mistakes:
4. At 10x scale, which component in an Active-Active failover system is most likely to become the bottleneck first, and why?
hard
A. Load balancers, because they cannot handle increased cross-datacenter traffic
B. Client applications, due to inability to handle multiple active endpoints
C. Passive nodes, because they become overwhelmed with failover requests
D. Replication protocol, due to increased conflict resolution overhead and network latency

Solution

  1. Step 1: Identify scaling challenges in Active-Active

    Active-Active requires continuous replication and conflict resolution across datacenters.
  2. Step 2: Analyze bottleneck at 10x scale

    Replication protocol overhead and network latency increase exponentially, causing delays and conflicts that bottleneck the system.
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Replication overhead -> first bottleneck at 10x scale [check]
Hint: Replication overhead grows fastest at scale [check]
Common Mistakes:
5. At 10x scale, which component is most likely to fail first and why when estimating system bandwidth for a social media platform with rapidly growing DAU?
hard
A. Storage Estimator, because disk I/O cannot keep up with 10x data volume growth
B. Bandwidth Estimator, because network metrics aggregation scales linearly and hits memory limits
C. DAU Estimator, because tracking and aggregating active users in real-time becomes a bottleneck
D. QPS Estimator, because load balancer metrics become too noisy and inaccurate at high scale

Solution

  1. Step 1: Identify bottleneck at 10x DAU scale

    DAU Estimator must track millions of active users in real-time, requiring heavy aggregation and state management.
  2. Step 2: Eliminate other options

    Storage Estimator scales with disk but can be sharded; Bandwidth Estimator aggregates metrics but less stateful; QPS Estimator uses load balancer metrics which scale better.
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    Real-time DAU tracking state grows fastest, causing bottleneck [check]
Hint: Real-time DAU tracking state grows fastest at scale [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