Part 7 of 8 · 3 min read
Scaling and trade-offs
Shard little, replicate more.
Scaling, caching and what to say
Business table. It may outgrow one server, so shard it, for example by business id.
Geospatial index table. Use one row per place and geohash, with a compound key of both. Adding or removing a place is then one simple row change with no locks. The alternative, a row per geohash holding a list of ids, needs the list to be fetched, scanned and locked for each change.
Do not shard too early. The whole geohash index is small, about the size of the quadtree, around 1.7 GB. It fits in one database server's memory. The problem is read load, not size. So add read replicas to spread reads. Sharding adds complexity, because a query would need to find data across shards.
Caching. Two cache layers are useful. Cache the result by geohash (a key of the geohash and the radius), since many users in one cell ask the same question. And cache place details by business id. The book notes that since changes take effect the next day, a nightly refresh is enough, but it warns that many keys expiring together can load the cache servers.
Availability. Run in several regions and zones, placing users with the nearest region, which also helps with privacy laws on where data lives.
Filters. To filter by open hours or place type, search by geohash first, then filter the small result in memory or in the database.
| Choice | Gain | Cost |
|---|---|---|
| Geohash in a table | Simple, easy updates | Fixed cell size |
| Quadtree in memory | Adapts to density, k nearest | Build time, harder updates |
| Read replicas | Simple read scaling | Replica lag |
| Cache by geohash | Fast, fewer queries | Slightly old data |
| Search 9 cells | Fixes edges | More rows to read |
Interview angle
Answer in your head first, then open it.
Why not a plain SQL range?
Two dimensions, and an index covers one.
How does geohash work?
It splits the map by bits, and names cells with strings.
What are the edge cases?
No shared prefix across lines, and cell borders. Search the neighbours too.
Geohash or quadtree?
Geohash is simpler, and quadtree adapts to density and finds k nearest.
Do you shard the index?
Probably not at first. Use replicas, since the data is small.
One follow-up to try. "Support moving users, like drivers on a map." A good reply: locations now change every few seconds, so a table in a disk database is too slow. Keep current positions in memory, in a geohash-keyed store, and drop old ones. This is a different problem from fixed places, because the writes become the main load.
Check yourself: 1. Why is one row per place and geohash easier to update? 2. Why not shard the index early? 3. What changes if places move?
Words you will meet
| Word | Meaning |
|---|---|
| Proximity service | Finds places near a point |
| LBS | A service that uses location |
| Geospatial index | An index that makes map searches fast |
| Geohash | A string naming a map cell |
| Quadtree | A tree that splits crowded map areas in four |
| Leaf node | A node with no children |
| Read replica | A copy of a database used only for reads |
| Geofence | A virtual boundary around an area |