System Design Interview

Wrap Up

Wrap up 1 min readLesson 4 of 4

In this chapter, we have presented the design for proximity service. The system is a typical LBS that leverages geospatial indexing. We discussed several indexing options:

  • Two-dimensional search

  • Evenly divided grid

  • Geohash

  • Quadtree

  • Google S2

Geohash, quadtree, and S2 are widely used by different tech companies. We choose geohash as an example to show how a geospatial index works.

In the deep dive, we discussed why caching is effective in reducing the latency, what should be cached and how to use cache to retrieve nearby businesses fast. We also discussed how to scale the database with replication and sharding.

We then looked at deploying LBS in different regions and availability zones to improve availability, to make users physically closer to the servers, and to comply better with local privacy laws.

Congratulations on getting this far! Now give yourself a pat on the back. Good job!

Chapter Summary

Reference Materials

  1. Yelp: https://www.yelp.com/
  2. Map tiles by Stamen Design: http://maps.stamen.com/
  3. OpenStreetMap: https://www.openstreetmap.org
  4. GDPR: https://en.wikipedia.org/wiki/General_Data_Protection_Regulation
  5. CCPA: https://en.wikipedia.org/wiki/California_Consumer_Privacy_Act
  6. Pagination in the REST API: https://developer.atlassian.com/server/confluence/pagination-in-the-rest-api/
  7. Google places API: https://developers.google.com/maps/documentation/places/web-service/search
  8. Yelp reservation API: https://docs.developer.yelp.com/docs/reservation
  9. Regions and Zones: https://docs.aws.amazon.com/AWSEC2/latest/UserGuide/using-regions-availability-zones.html
  10. Redis GEOHASH: https://redis.io/commands/GEOHASH
  11. POSTGIS: https://postgis.net/
  12. Cartesian tiers: http://www.nsshutdown.com/projects/lucene/whitepaper/locallucene_v2.html
  13. R-tree: https://en.wikipedia.org/wiki/R-tree
  14. Global map in a Geographic Coordinate Reference System: https://bit.ly/3DsjAwg
  15. Base32: https://en.wikipedia.org/wiki/Base32
  16. Geohash grid aggregation: https://bit.ly/3kKl4e6
  17. Geohash: https://www.movable-type.co.uk/scripts/geohash.html
  18. Quadtree: https://en.wikipedia.org/wiki/Quadtree
  19. How many leaves has a quadtree: https://stackoverflow.com/questions/35976444/how-many-leaves-has-a-quadtree
  20. Blue green deployment: https://martinfowler.com/bliki/BlueGreenDeployment.html
  21. Yext: Maps and Location Support: https://www.yext.com/platform/features/maps-and-location-support
  22. S2: http://s2geometry.io/
  23. Hilbert curve: https://en.wikipedia.org/wiki/Hilbert_curve
  24. Hilbert mapping: http://bit-player.org/extras/hilbert/hilbert-mapping.html
  25. Geo-fence: https://en.wikipedia.org/wiki/Geo-fence
  26. Region cover: http://s2geometry.io/devguide/s2cell_hierarchy
  27. Bing map: https://bit.ly/30ytSfG
  28. MongoDB: https://docs.mongodb.com/manual/tutorial/build-a-2d-index/
  29. Geospatial Indexing: The 10 Million QPS Redis Architecture Powering Lyft: https://www.youtube.com/watch?v=cSFWlF96Sds&t=2155s
  30. Geo Shape Type: https://www.elastic.co/guide/en/elasticsearch/reference/1.6/mapping-geo-shape-type.html
  31. Geosharded Recommendations Part 1: Sharding Approach: https://medium.com/tinder-engineering/geosharded-recommendations-part-1-sharding-approach-d5d54e0ec77a
  32. Get the last known location: https://developer.android.com/training/location/retrieve-current#Challenges

Finished reading?

Mark it complete to track your progress.

PreviousDesign Deep DiveProximity ServiceNext Understand the ProblemNearby Friends