Every Query Hit All 18 Shards. Then We Bent the Index Around the Planet.

A menu search is a radius query wearing a costume

One of the platforms we work on indexes restaurant menus down to the individual dish, with allergens, diets, cuisines, ingredients and nutrition for each one. Users can filter on all of that, but the product question is almost always the same one: what can I eat near here?

The data lives in OpenSearch: around 55 million dishes (menu items) from roughly 650,000 restaurant locations. Restaurants are parent documents with a location, and dishes are child documents joined to them, so a dish search can filter on its restaurant's location without copying coordinates onto 55 million documents. A typical search asks for dishes within a radius around the user, plus the counts that feed the filter sidebar.

The query itself was fine. The problem was where OpenSearch sent it.

By default, OpenSearch picks a document's shard by hashing its ID. The hash ignores everything about the document, which keeps shards evenly sized, but it also means restaurants in San Francisco are spread across all 18 shards of the index. So a search around San Francisco has to ask all 18. Each shard, holding roughly three million dishes, filters its slice of the data, builds the sidebar counts and returns its best matches, and the coordinating node waits for every one of them before merging. Most of those shards have no restaurants anywhere near San Francisco. They do the work anyway.

OpenSearch lets you pass a routing value to send a query to specific shards. That's easy when a query is about one thing, like a single restaurant. A radius search is about an area, so we needed a way to turn an area into a short list of shards.

Borrowing the trick from Tinder

We didn't invent this. Tinder described the approach in Geosharded Recommendations Part 1: Sharding Approach. Their recommendations are always local, so they place data on shards by location and, at query time, work out which shards a search area can touch.

Our version of the problem is simpler than theirs. Tinder's users travel, so a profile's shard can change whenever its owner does. Restaurants don't move. Once a location lands on a shard it stays there, along with all of its dishes, and documents only change shards when we decide to redraw the boundaries.

The idea fits in a sentence. Making it work means answering two questions:

1. How do you turn a point on the globe into a key that sorts, so that places close to each other get keys close to each other?
2. Where do you cut that key space, when a handful of metro areas hold most of the restaurants and huge areas hold none?

For the first one we used Google's S2 geometry library, like Tinder did. The answer to the second came from our own data.

Turning a location into a sortable key

S2 puts the globe inside a cube and projects every point onto one of the cube's six faces. Each face is split into four cells, each of those into four again, and so on, 30 levels deep. We use level 10, where a cell covers about 81 km² on average (S2 cell statistics). Roughly a neighbourhood.

The useful part is how the cells are numbered. Instead of going row by row, S2 numbers them along a Hilbert curve, a line that snakes through every cell on a face without ever jumping. Cells that are close on the curve are close on the map. Each cell gets a 64-bit ID, usually written as a short hex string called a token. Downtown San Francisco, for example, sits in the level-10 cell 808581.

Because tokens follow the curve, sorting them keeps neighbours together, and a continuous range of tokens is a continuous patch of the map. That's the shape you want a shard to be.

The globe below shows this structure, colored by the shard each area belongs to. It stops at level 5, since level 10 is too fine to draw. Set the level to 5, switch on the Hilbert layer and follow the curve across a face: it never jumps, and the colors change along it in order. Then rotate to North America and look at where the colors break along the edge of a face.

Plate I  ·  The S2 cell hierarchy, colored by sharddrag to rotate

−100%+

flatten

Cell level

drawn atL4 · 1,536 cells

Layers

shardshilbertgridlandspin

Point under cursor

lat / lon

—

token L10

—

shard

—

Equal area is the wrong answer

Once locations sort, sharding comes down to where you draw the boundaries. The obvious move is to cut the map into equal-sized ranges. That gives you a few shards drowning in big-city menus and plenty of shards holding ocean and empty land.

So we weighted the map. Every level-10 cell got one point per restaurant plus one per dish, since dishes are what actually fill the index. A small script then walked the cells in key order, filling a shard until it reached a target size and then starting the next one. It tried every target size that would produce between 12 and 36 shards and kept the split where the shards came out most even.

On our data that meant 17 boundaries, so 18 shards. Nobody picked the number; it came out of the data.

Each shard got a name instead of a number. yankee,zenith,titan in a slow-query log tells you straight away that someone searched around New York. 13,14,15 doesn't.

This is how the split came out, with a set of US cities placed on their shards:

Two things stand out.

The busiest areas get the narrowest shards. zulu covers ten of the sample cities, from Cheyenne to Memphis, while the New York area is split across yankee, zenith and apollo. zenith is so narrow that none of the 63 sample cities falls inside it. That's the balancing doing its job.

The other one looks like a bug. ares holds Minneapolis, Fargo, Billings and Burlington, Vermont, and nova holds Seattle, San Francisco, Honolulu and Anchorage. Those aren't neighbours, and the cube is the reason. The northern states sit on a different cube face from the rest of the country, and Hawaii sits on a third. The Hilbert curve keeps things together within a face, not across the edges between faces. In practice this costs very little: a search near an edge covers cells on both sides and simply asks both shards.

Every dish follows its restaurant

When a document is indexed, its shard comes from its location. Take the restaurant's coordinates, find the level-10 cell, and check which range that cell's token falls into.

Dishes always use their restaurant's location, never anything of their own. That part isn't optional: OpenSearch requires parent and child documents to be on the same shard for joins to work. Routing by location gives us that for free, and every dish ends up on the shard that covers the place you can order it.

From a search circle to a handful of shards

At search time it works in reverse. The API takes the search circle (or the visible map area), asks S2 for the level-10 cells that cover it, looks up the shard for each cell, and sends the query only to that set of shards.

The number of cells can be large, but the number of shards stays small. A 15-mile search around San Francisco covers 40 cells, and all 40 belong to nova. The same search around New York, the densest part of the map, covers 38 cells and asks just two shards, yankee and zenith. Widen the San Francisco search to 25 miles and six of its 98 cells spill onto roger, so it asks two as well. Neighbouring cells sit close together on the curve, so they fall into the same few ranges.

Boundaries do land in awkward places. The line between nova and roger runs through the South Bay: Mountain View is on nova, and Palo Alto, right next door, is on roger. A 15-mile search around San Jose covers 38 cells, 21 on roger and 17 on nova. It still asks two shards instead of eighteen.

The location filter still runs on every shard that gets asked. Routing only decides where to look. The cells deliberately overshoot the circle, so the worst a generous covering can do is ask one extra shard, and the filter still decides which restaurants are actually inside the radius.

Try it below. Pick San Francisco at 15 miles and only one segment of the shard bar lights up. Drag the radius to 25 and a second one joins as the edge of the circle crosses into roger. Then switch to New York and push the radius to 50 miles to see a dense area spread across five.

Plate II  ·  Covering a search radius with level-10 cells—

Search centre

San FranciscoLos AngelesDallasMiamiNew YorkChicago

Radius

miles25

Result

cells

0

shards

0 / 18

routing

—

Index shards

ares

nova

roger

mars

thor

whiskey

zulu

bravo

sierra

echo

lambda

tango

alpha

titan

yankee

zenith

apollo

tudor

A few more searches, worked out the same way:

What it costs

Geosharding cuts the number of shards a local search touches, but you pay for it in other places.

The shard boundaries have to be identical everywhere documents are written and everywhere they're searched. If they drift apart, a document gets written to one shard and looked for on another. Nothing throws an error. The search just comes back empty, which looks exactly like a normal empty result.

The boundaries also reflect the data at the moment they were computed. Menus don't grow evenly, so over time some shards get heavier than others. Moving a boundary changes where documents belong, and OpenSearch can't move documents between shards, so rebalancing means reindexing.

Not every search benefits either. A 50-mile search around New York already touches five shards, and a search with no location still goes to all 18. Geosharding helps the common local search and leaves the rest as they were.

And every write has to carry the routing key. A document indexed without it lands on whichever shard its ID hashes to, where routed searches will never look. For the lookups where a missing document would really hurt, we keep a slower fallback that searches every shard.

When it's worth it

Geosharding pays off when nearly every query is tied to an area, the index is big enough that per-shard work adds up, and the data is uneven enough that splitting by area doesn't work. Menu search checks all three. A global text search over the same index wouldn't gain anything, because there's no area to cover.

If your search looks like ours, the parts worth copying are: let the data choose the shard count, weight by whatever actually fills the index, keep the location filter even when you route, and give your shards names.

None of it needs a custom partitioner or an extra service. It's the S2 library, one balancing script, and a list of 17 boundaries that has to stay the same everywhere the index is read or written.

References:

• Geosharded Recommendations Part 1: Sharding Approach, Tinder Tech Blog
• S2 Geometry and its cell statistics
• OpenSearch join field type
• OpenSearch _routing field