mufassall

Data & storage / 3 / 15

Geo search: who is nearby

A taxi app must find the ten nearest free drivers around a rider, while 50 000 drivers send their position every 4 seconds. Why a normal index does not help, and how geohash, neighbour cells, a quadtree and S2/H3 cells answer "who is within 2 km" in milliseconds.

  • 14 min
  • Intermediate
  • 11 steps
Search p95
900 ms
Drivers read
50 000
Nearest missed
0 %
Ghost drivers
0
Open in Lab

70%95%
  • request
  • reply
  • redelivery
  • duplicate
  • lost

Numbers are a model scenario, not measurements

The real request

Matching API → Drivers DB

Request

SELECT id, lat, lng FROM drivers
WHERE status = 'free'
  AND distance_km(lat, lng, 41.3110, 69.2797) < 21
ORDER BY distance_km(lat, lng, 41.3110, 69.2797)
LIMIT 10;

Response

10 rows, Seq Scan on drivers2
rows examined: 50000, time: 780 ms3
  1. distance_km — A function of the row's values. No ordinary index can answer it in advance.
  2. Seq Scan — The plan reads the whole table, row by row.
  3. examined — 50 000 rows read to return 10. Almost all of the work is wasted.

Build it yourselfCheat sheetCompare lessons

Course: 74 lessons
  1. 01 Foundations

    1. The life of a request
    2. Latency and throughput
    3. Napkin math
  2. 02 Scaling

    1. Scaling up vs scaling out
    2. Load balancing
    3. Stateless servers
    4. Caching
    5. Cache invalidation
    6. CDN and edge caching
  3. 03 Data & storage

    1. SQL and NoSQL
    2. Database indexes
    3. Geo search: who is nearby
    4. Full-text search
    5. Vector search
    6. Storage engines: B-tree and LSM
    7. Bloom filters
    8. Database replication
    9. Sharding
    10. Consistent hashing
    11. Unique IDs
    12. CAP: when the link breaks
    13. Consensus and leader election
    14. Transactions
    15. File uploads
  4. 04 Communication

    1. API styles
    2. Message queues
    3. Pub/sub and event logs
    4. Real-time updates
    5. Reliable callbacks
    6. Sending webhooks reliably
  5. 05 Reliability

    1. Redundancy and failover
    2. Rate limiting
    3. Timeouts and retries
    4. Observability
    5. SLOs and error budgets
    6. Backpressure
  6. 06 Architecture

    1. Microservices
    2. Service discovery
    3. Sagas and the outbox
    4. Change data capture (CDC)
    5. Transactional outbox
    6. Distributed locks
    7. Batch vs stream
    8. Multi-tenancy
    9. Event sourcing
  7. 07 Security

    1. Authentication
    2. Authorization
    3. Encryption and secrets
    4. Secrets management
  8. 08 Shipping

    1. Testing
    2. CI/CD: from commit to production
    3. Zero-downtime migrations
    4. Feature flags
  9. 09 Whole systems

    1. From requirements to design
    2. Design a URL shortener
    3. Design a news feed
    4. Design a chat
    5. Design a video streaming site
    6. Design search autocomplete
    7. Design a job scheduler
  10. 10 Business processes

    1. Payment gateway
    2. Money and rounding
    3. Double-entry ledger
    4. Payment reconciliation
    5. Subscription billing
    6. Electronic digital signature
    7. Document lifecycle
    8. Audit log
    9. Notification delivery
    10. Bulk import
    11. Refunds and chargebacks
    12. Gapless document numbering
  11. 11 Case studies

    1. Case: how Discord stores messages
    2. Case: Figma multiplayer editing