Geosharding: Splitting a Location Search With S2 Cells, Load Containers and Ordered Updates
Why one global index fails for nearby-people search, how S2 cells and the Hilbert curve give contiguous shards, and how to keep moving users consistent.
On this page
A person in Los Angeles never needs a candidate from London, yet a single global index makes every query pay for both. As the index grew, searches slowed, replicas multiplied and the bill climbed. The fix is not a faster index, it is a smaller one chosen by where the user is.
The single-index problem
| Symptom | Cause |
|---|---|
| Slow searches | Every query scans or filters across data from the whole world |
| Rising cost | More and bigger nodes and replicas needed just to hold speed |
| Hard to scale | One index becomes a single, enormous unit of operation |
The idea: shard by place
Divide the map into regions, one shard per region. A query for a 50 mile radius needs the shard or two covering that circle, not the planet. Three gains follow: relevant-only searching, smaller shards that are faster to query and operate, and better resource use. Reported effect: roughly twenty times more computation handled with low latency.
How big should a shard be?
The right size balances three forces.
S2 cells: dividing the globe
Google’s S2 library divides the sphere into a hierarchy of cells. Each cell splits into four children (a quadtree), so you can represent anything from a continent to a street corner by choosing a level.
Properties that make it fit sharding:
- Roughly equal cell areas at the same level, avoiding the distortion near the poles that hurts geohash grids.
- Spatial locality via a Hilbert curve. Cell ids follow a space-filling curve, so cells that are close on the map are close in id order. Los Angeles and San Diego sit near each other in the ordering, which lets you slice contiguous ranges into shards.
- Choice of granularity. In the reported setup, level 7 cells (about 45 miles across) suited sparse areas and level 8 (about 22 miles) suited dense ones like large cities.
- Fast geo-queries. Built-in functions map a coordinate to its cell, and a circle to the set of cells covering it.
Balancing: load containers
Equal area does not mean equal work, so each cell gets a load score: active users, query volume. Then:
- Order cells along the curve
Walking cells in Hilbert order keeps neighbours together.
- Fill a container until it hits the load threshold
Add adjacent cells to a container, summing their load scores.
- Seal the container as one shard
When the threshold is reached, start the next. Each shard is geographically contiguous and carries roughly equal load, large rural areas in one shard, a dense city split into many.
The abstraction layer
Applications should not know which shard anything is in. A small internal service sits in front of the search cluster and owns that knowledge.
| Responsibility | What it does |
|---|---|
| User-to-shard mapping | Keeps a map of which shard holds each user |
| Location updates | On a move, decides whether the user crosses a shard boundary, removes the record from the old shard and adds it to the new |
| Query routing | Computes which shards cover the user’s location plus distance filter, fans the query out, merges and ranks results |
| Re-sharding | Lets shard boundaries change as density shifts, without application changes |
Multi-index or multi-cluster?
Put each geoshard in its own index inside one cluster, or build a separate cluster per shard? The single cluster with multiple indices won: cross-cluster querying is limited and per-cluster maintenance multiplies. To prevent uneven load in a single cluster:
- Adjust replica counts per shard: busy city shards get more replicas, quiet ones fewer.
- Temporarily raise replicas for a hotspot.
- Spread replicas across nodes for failure tolerance.
Using time zones as a free load balancer
A shard’s traffic peaks in its local evening. If the New York shard and the Tokyo shard share a server, that server’s busy times are spread across the day. So shards and replicas are placed randomly across nodes, mixing different time zones on each. No one node gets every peak at once.
Cluster roles
| Node role | Job |
|---|---|
| Master | Tracks the cluster state and where shards live, reassigns shards on failure. Handles no user queries |
| Coordinating | Receives requests, determines which shards to query, gathers and merges results |
| Data | Stores primary and replica shards, executes the queries |
Keeping moving users consistent
Users jump between locations, so moves race with each other: switch to another city and immediately back, a write fails mid-migration, a shard mapping lags behind the data.
Lessons for any proximity feature
Do
Shard by locality with equal load, not equal area, keep a routing layer so shards can change, reduce migration churn with sensible cell sizes, and make an ordered stream the only path that changes where a record lives.
Don't
Add replicas to a global index forever. You are paying to search data that, for this query, is irrelevant by definition.
Takeaway
Location search is a locality problem, and sharding by place turns a global scan into a handful of small queries. S2 cells and a Hilbert ordering give contiguous, balanceable regions, a routing layer hides the layout, randomised placement exploits time zones, and an ordered update stream with periodic reconciliation keeps travelling users coherent.
Frequently asked questions
What is geosharding?
Partitioning data by geographic region so a query for nearby items touches only the shards covering that area. Instead of searching one huge global index, the system searches a few small ones, which cuts latency and cost. The challenge is choosing region sizes and moving records when users travel.
What is an S2 cell?
A region of the Earth's surface from Google's S2 geometry library, arranged in a hierarchy where each cell splits into four. Cells at one level are roughly equal in area, and the library maps a latitude and longitude to a cell quickly. Nearby places get nearby cell ids thanks to a space-filling curve.
Why use S2 or the Hilbert curve instead of geohash?
Geohash cells distort toward the poles and have discontinuities where adjacent places receive very different codes. S2 cells are more uniform in size, and the Hilbert ordering keeps nearby cells numerically close, which makes grouping contiguous cells into balanced shards straightforward.
How do you keep a moving user's data consistent across shards?
Route every update for a user through one ordered stream, for example a Kafka partition keyed by user id, so updates apply in order. Use real-time get-by-id reads where freshness matters, and run a periodic reconciliation that re-syncs the search index from the source of truth.

/* Comments */
Comments are offline right now — we reconnect automatically, nothing is lost.