CSE Roadmap

Core tier · about 4 hours · 8 parts

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