Bird
Raised Fist0

Yelp / Proximity Service - Geohash, Quadtree, Nearby Search

HLDhardInterview freq: medium
Choose your preparation mode4 modes available
ArchitectureTraceChallenge
🎯
Design Yelp / Proximity Service - Geohash, Quadtree, Nearby Search
45 min · senior
senior

You are designing a proximity search service for a startup with 50 million daily active users (DAU). Users query for nearby places (restaurants, shops, etc.) with a P99 latency under 200ms. The system must support encrypted data at rest and in transit, handle frequent location updates, and provide strong consistency for search results. The service should scale to handle millions of queries per second and support geo-based filtering and sorting.

Constraints
  • P99 query latency under 200ms at 50M DAU
  • Data encrypted at rest and in transit (TLS + disk encryption)
  • Support 10 million location updates per minute
  • Strong consistency for nearby search results
  • Handle geo queries with radius and bounding box filters
  • System must degrade gracefully under load without data loss
📋
Guided Steps
1/6
Step 1
Choose the spatial indexing technique
Which spatial indexing method will you use to efficiently support nearby search queries at scale?
💡 Hint
Consider hierarchical spatial partitioning that supports range queries and dynamic updates.
Key Decision
Use Geohash combined with a Quadtree index stored in Apache Cassandra - Geohash prefixes enable fast prefix scans, Quadtree supports hierarchical spatial filtering, and Cassandra scales linearly with partition keys.
Interviewer Expectation
Mid: Names Geohash or Quadtree. Senior: Explains combining Geohash prefix scans with Quadtree hierarchical filtering for efficient range queries and why Cassandra's partition key design supports scale.
⚠️Common Wrong Answer
Using only a relational database with spatial indexes like PostGIS - fails at 50M DAU due to poor horizontal scalability and high write latency.
Step 2
Design data storage and partitioning
How will you store and partition place and location data to support high write throughput and low-latency queries?
💡 Hint
Think about partition keys that localize queries and enable efficient range scans.
Key Decision
Store place metadata and geohash-indexed location data in Apache Cassandra with partition key = geohash prefix (e.g., first 6 chars) to localize queries and clustering key = place_id for uniqueness and range scans.
Interviewer Expectation
Mid: Mentions Cassandra for scalability. Senior: Explains geohash prefix as partition key to co-locate spatially close data and why alternative keys (e.g., place_id alone) cause scatter and high latency.
⚠️Common Wrong Answer
Using a single global partition key or random UUID partition keys - causes scatter across nodes, increasing query latency and reducing cache hit rates.
Step 3
Handle location updates and data consistency
How will you ingest frequent location updates and ensure strong consistency for search results?
💡 Hint
Consider write path, data replication, and read-after-write consistency guarantees.
Key Decision
Use Apache Kafka as a durable ingestion pipeline for location updates, processed by stateless workers that update Cassandra with QUORUM consistency level reads/writes to ensure strong consistency and low latency.
Interviewer Expectation
Mid: Names Kafka for ingestion. Senior: Explains why Kafka partitions keyed by geohash prefix ensure ordered updates per region and why Cassandra QUORUM consistency balances latency and correctness.
⚠️Common Wrong Answer
Direct writes from clients to Cassandra without buffering - leads to write amplification, hotspots, and inconsistent reads under high load.
Step 4
Design query API and caching layer
How will you design the nearby search API and optimize for P99 latency under 200ms?
💡 Hint
Think about query parameters, caching hot regions, and fallback strategies.
Key Decision
Expose a REST API supporting radius and bounding box filters with geohash prefix queries; use Redis as a read-through cache for hot geohash partitions with TTL-based invalidation to reduce Cassandra load and meet latency SLAs.
Interviewer Expectation
Mid: Describes basic REST API. Senior: Details geohash prefix filtering, Redis caching strategy with TTL and cache warming, and fallback to Cassandra on cache miss.
⚠️Common Wrong Answer
No caching or using a global cache key - causes cache misses and high backend load, increasing latency beyond 200ms.
Step 5
Ensure security and encryption
How will you enforce encryption and secure data in transit and at rest?
💡 Hint
Consider TLS, disk encryption, and key management.
Key Decision
Use TLS 1.3 for all client-server and inter-service communication; enable AES-256 disk encryption on Cassandra nodes; manage encryption keys via AWS KMS with automatic rotation.
Interviewer Expectation
Mid: Mentions TLS and disk encryption. Senior: Explains TLS 1.3 benefits, encryption key lifecycle management with KMS, and impact on latency and operational complexity.
⚠️Common Wrong Answer
Relying only on network-level security without disk encryption - risks data exposure if disks are compromised.
Step 6
Plan for graceful degradation and failure handling
How will the system behave under load spikes or partial failures to avoid data loss and maintain availability?
💡 Hint
Think about backpressure, circuit breakers, and fallback modes.
Key Decision
Implement backpressure in Kafka consumers, circuit breakers in API gateway to reject excess queries, and degrade to cached stale data with TTL fallback to maintain availability without data loss.
Interviewer Expectation
Mid: Mentions retries or rate limiting. Senior: Explains backpressure propagation from Kafka consumers to producers, circuit breaker patterns, and stale cache fallback to maintain SLA under overload.
⚠️Common Wrong Answer
No backpressure or circuit breakers - leads to cascading failures and system collapse under load.
🔌
API Design Challenge
Sketch 3 core API endpoints for the proximity service: how clients send location updates, query nearby places, and acknowledge receipt of search results.
Hints
  • How does the client send location updates efficiently and securely?
  • What parameters and filters should the nearby search endpoint support?
  • How does the system confirm delivery or processing of search results?
📊
Scoring Rubric
▼ Show
Must Have - 60%
  • Use of hierarchical spatial indexing (Geohash + Quadtree) for efficient geo queries
  • Partitioning data in Cassandra by geohash prefix to localize queries and scale writes
  • Kafka ingestion pipeline keyed by geohash prefix for ordered, scalable updates
  • Caching layer (Redis) to reduce backend load and meet strict latency SLAs
  • Encryption in transit and at rest with TLS 1.3 and AES-256 disk encryption
Good to Have - 30%
    Bonus - 10%
      Anti-patterns to Avoid
      ✅
      Model Answer
      ▼ Reveal

      This design uses a combination of Geohash and Quadtree spatial indexing stored in Apache Cassandra to support efficient, scalable proximity searches for 50M DAU with strong consistency and low latency. Location updates are ingested via Apache Kafka keyed by geohash prefix to ensure ordered processing and durability. A Redis read-through cache reduces backend load and helps meet the 200ms P99 latency SLA. Security is enforced with TLS 1.3 and AES-256 disk encryption managed by AWS KMS. The system implements backpressure and circuit breakers to gracefully handle load spikes and failures.

      Key Decisions
      • Use Geohash prefixes combined with Quadtree hierarchical filtering for efficient range queries
      • Partition Cassandra data by geohash prefix (first 6 chars) with clustering key place_id for localized queries and scalability
      • Ingest location updates via Kafka keyed by geohash prefix to ensure ordered, durable writes
      • Use Cassandra QUORUM consistency level for reads and writes to guarantee strong consistency
      • Implement Redis as a read-through cache with TTL-based invalidation to reduce Cassandra load and meet latency SLAs
      • Enforce TLS 1.3 for all client-server and inter-service communication and AES-256 disk encryption with AWS KMS key management
      • Apply backpressure in Kafka consumers and circuit breakers in API gateway to reject excess queries and degrade gracefully to stale cached data
      • Geohash + Quadtree spatial indexing for efficient hierarchical geo queries
      • Apache Cassandra with geohash prefix partition key for scalable, localized data storage
      • Apache Kafka for durable, ordered ingestion of location updates keyed by geohash prefix
      • Redis read-through cache with TTL for hot geohash partitions to meet 200ms P99 latency
      • TLS 1.3 for encryption in transit and AES-256 disk encryption with AWS KMS for key management
      • REST API supporting radius and bounding box filters with pagination and sorting
      • Backpressure and circuit breaker patterns to gracefully handle load spikes and failures
      • Strong consistency via Cassandra QUORUM reads/writes to ensure up-to-date search results

      Practice

      (1/5)
      1. A distributed cache system needs to evenly distribute keys across servers and minimize data reshuffling when nodes are added or removed. Which component best handles this requirement?
      easy
      A. A simple modulo-based hash function assigning keys to servers by key % server_count
      B. A centralized directory service mapping keys to servers explicitly
      C. A consistent hashing ring with virtual nodes to balance load and reduce remapping
      D. A random key assignment with periodic rebalancing of all keys

      Solution

      1. Step 1: Understand key distribution and remapping

        Modulo-based hashing (A simple modulo-based hash function assigning keys to servers by key % server_count) causes massive remapping when server count changes, violating minimal reshuffling.

      2. Step 2: Evaluate consistent hashing with virtual nodes

        Consistent hashing with virtual nodes (A consistent hashing ring with virtual nodes to balance load and reduce remapping) evenly distributes keys and minimizes remapping on node changes.

      3. Final Answer:

        Option C -> Option C

      4. Quick Check:

        Virtual nodes in consistent hashing minimize key remapping on node changes [check]
      Hint: Virtual nodes smooth load, minimize reshuffle [check]
      Common Mistakes:
      2. For a distributed database with high write throughput and large keyspace, which approach to Bloom filter design best balances memory usage and false positive rate?
      medium
      A. Use a single global Bloom filter for all keys to minimize memory overhead
      B. Use partitioned Bloom filters per data shard to localize false positives and reduce memory per filter
      C. Use counting Bloom filters everywhere to allow deletions despite higher memory cost
      D. Use a cache of recently accessed keys instead of Bloom filters to reduce false positives

      Solution

      1. Step 1: Analyze memory and false positive trade-offs

        A single global Bloom filter grows large and has higher false positive rates due to keyspace size; partitioning per shard reduces filter size and localizes false positives.

      2. Step 2: Evaluate alternatives

        Counting Bloom filters allow deletions but consume more memory, which is costly at large scale; caching recent keys does not guarantee absence and can miss cold keys.

      3. Final Answer:

        Option B -> Option B

      4. Quick Check:

        Partitioned Bloom filters balance memory and false positives at scale [check]
      Hint: Partition filters localize false positives, save memory [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. For storing aggregated logs with fast query response and cost efficiency, which storage architecture is best when logs are mostly write-once and rarely updated?
      medium
      A. Use a distributed relational database with strong consistency
      B. Use a NoSQL key-value store with frequent compactions
      C. Use a columnar data warehouse optimized for append-only writes
      D. Use a distributed file system with manual indexing

      Solution

      1. Step 1: Analyze log storage requirements

        Logs are write-once, large volume, and require fast analytical queries.

      2. Step 2: Evaluate columnar data warehouse

        Columnar stores optimize for append-only writes and fast scans, reducing cost and improving query speed.

      3. Final Answer:

        Option C -> Option C

      4. Quick Check:

        Columnar warehouse -> optimized for append-only and analytics [check]
      Hint: Columnar storage excels at append-only analytics [check]
      Common Mistakes:
      5. At 10x scale, which component in a TCP-based chat system is most likely to fail first and why?
      hard
      A. The chat servers, because maintaining many TCP connections consumes memory and CPU per connection
      B. The database, because increased writes cause locking and slow queries
      C. The load balancer, because it cannot distribute TCP connections evenly
      D. The network switches, because TCP traffic overwhelms routing tables

      Solution

      1. Step 1: Identify stateful components at scale

        Chat servers maintain stateful TCP connections, each consuming resources like memory and CPU.

      2. Step 2: Analyze scaling impact

        At 10x scale, the number of concurrent TCP connections overwhelms server resources, causing failures before database or network components.

      3. Final Answer:

        Option A -> Option A

      4. Quick Check:

        Stateful TCP connections -> chat servers bottleneck first [check]
      Hint: Stateful TCP connections -> chat servers bottleneck first [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