System design practice

Nearby Search

hard Based on a system published by Tinder geo sharding search hot-partitions real-world

Tinder's geosharded search: S2 cells grouped by load, so a search reads only the few geoshards near it.

Solve it in your browser Read the lesson first

Tinder shows each user a stack of people nearby: within the distance they chose (at most 100 miles), matching their filters. Everyone searchable lives in Elasticsearch. At first that was one cluster with one index and the default five shards, scaled with more replicas and bigger nodes until CPU and cost were too high: every search worked through users on other continents only to filter them out.

Tinder's fix was to shard the index by location. The map is divided into S2 cells (Google's hierarchical cells on the sphere). Nearby cells are grouped into geoshards, and the grouping balances load, not area: a dense metro is split into several small geoshards, while a sparse region far bigger shares one. A search turns its circle into the cells that cover it and reads only the few geoshards those cells belong to. Design the search, the router in front of the geoshards, and the path that keeps the index up to date as people move.

Functional requirements

Use these ids, use case and scenario names exactly: the traffic, requirements and tests in problem.proschi refer to them.

Scale

Tinder's posts report 40 to 100 geoshards worldwide and an example where a 100-mile search reads 3 of 55 geoshards. The rates, the 40% share, the 5% of moves and the 7 geoshards here are assumptions for the exercise.

Constraints

What is given

problem.proschi declares the client, app, and profiles, the source of truth for profiles and locations (DynamoDB, x3). Add the API, the geo router, the two geoshard groups (Elasticsearch; their shard counts, with capacity { metro shards 3 }, are yours to choose), the change stream, the indexer and the three use cases.

What this model leaves out

Based on

The series lists Frank Ren, Xiaohu Li, Devin Thomson and Daniel Geng as authors.

How your design is checked

You write the design as text in Proschi. Tests run in your browser: a simulation of the traffic above checks latency, availability, cost and what happens when a machine fails. How the simulation works.

Start designing

Lesson · 13 min read

Learn it: Nearby Search #

Nearby search: geoshards balanced by load #

What you'll learn #

The problem, explained #

A dating app shows each user people nearby: within the distance they chose, filtered by age and other preferences. The candidates come from a search index of every active user, with their location and the fields the filters need. The profile store stays the source of truth; the index is a copy built for this one question.

Tinder first kept that index in one Elasticsearch cluster with one index and the default five shards, and scaled it with more replicas and bigger nodes until CPU and cost were too high. Every search had to work through users across the whole world to keep the few within the radius (at most 100 miles). Their engineering blog describes the fix: shard the index by location into geoshards, built from S2 cells and balanced by load, so that a search reads only the geoshards near the searcher.

The problem has three use cases:

The tests check that searches go through the router and never read profiles, that a search stays inside one group, that location updates never call the index, that a move deletes the user from the old geoshard and upserts them into the new one, and that every geoshard has a replica.

Back-of-the-envelope #

searches
6k / s
geoshard searches, at 3 per search
18k / s
location updates
3k / s
7 geoshards × 3 copies
21 nodes
a month for the reference design
$12,300

Tinder's posts give 40 to 100 geoshards worldwide and an example where a 100-mile search reads 3 of 55; the rates, the 40% metro share and the 7 geoshards here are assumptions for the exercise.

FlowRateWhere it lands
Recommend, dense metro2.4k/s7.2k geoshard searches/s on metro
Recommend, elsewhere3.6k/s10.8k geoshard searches/s on regional
Update location3k/sAPI, profiles (writes), the stream
Index location3k/sindexer; 1.35k writes/s on metro, 1.8k on regional

The metro group. 7.2k searches and 1.35k writes a second is 8.55k requests. At about 3k a node, that is under 3 nodes of pure work. Three geoshards with three copies each is 9 nodes at about 32% busy. Lose one copy and that geoshard's 2.85k a second falls on two nodes: about 48%.

The regional group. 10.8k searches and 1.8k writes is 12.6k requests. Four geoshards of three copies is 12 nodes at 35%, and 53% after a loss.

Sharded by user id instead. Every search must visit all 7 shards, so each shard serves all 6k searches a second, whatever the shard count. Two copies would be 100% busy before a single write; four copies of 7 shards is 28 nodes, $11,200 for the index alone, and the budget is gone.

The rest. The API takes 9k requests a second at 2k per instance: 8 instances at 56%. The router takes 6k: 6 instances at 50%. The indexer handles 3k: 4 instances at 38%.

Concepts #

Search the index, not the database #

"Everyone within 50 miles, aged 25 to 35" is a range query over two coordinates plus filters. A key-value profile store is built to fetch a user by id; asked for a box of latitudes and longitudes it can only scan, and every scan competes with the location writes on the source of truth.

So the searchable fields live twice: in profiles as the truth, and in a search index built for location and filter queries. The index is allowed to lag by a second or two; a profile shown a moment after its owner moved is harmless.

Why one big index stops scaling #

An index too big for one node is split into shards. The question is which field decides the shard. The usual default, a hash of the user id, spreads users evenly, and that is exactly the problem: neighbours end up on every shard, so a search for "near me" has to ask every shard and merge the answers. This is scatter-gather.

Scatter-gather has two costs. Each shard serves every search, so adding shards adds work per search, never capacity; only more copies of each shard help. And the search waits for the slowest of all the shards, so its tail latency grows with the shard count.

The way out is to shard by the field the query filters on. Searches filter on location, so the index should be split by location.

S2 cells #

To shard by location, you need a way to name a piece of the map. Google's S2 library projects the sphere onto the six faces of a cube and divides each face into a hierarchy of cells: each cell splits into four children, through 31 levels (0 to 30), from a whole face down to about a square centimetre. Every cell has a 64-bit id, and the ids follow a Hilbert curve, so cells that are close on the map are usually close in id order.

S2 gives two operations a nearby search needs. One maps a point to the cell that contains it, at any level: that is where a user is indexed. The other covers a region: given a circle around the searcher, it returns a small set of cells that together contain it. Cells at the same level have roughly the same area anywhere on Earth, unlike a latitude-longitude grid, whose cells shrink towards the poles.

Deep dive S2 or geohash?

A geohash also names cells with a string whose prefix gets shorter as the cell grows, and it works as a plain database key. Its cells are rectangles in latitude and longitude, so their size changes with latitude, and its curve jumps more at cell edges. S2's cells are close to equal area and its covering function returns a tight set of cells for a circle. For this problem either names cells; what matters is the next step, grouping cells into geoshards.

Geoshards balanced by load #

The simplest way to cut the map is into equal pieces: every geoshard the same number of cells. It fails on the first city. Users are packed into metros, and so are searches, so the geoshard over a big city gets a large share of the whole load while geoshards over oceans and deserts sit idle. That is a hot shard, and adding nodes to the cluster does not cool it.

Tinder groups cells by load instead. Each cell (S2 level 7 or 8) gets a score from its unique users, active users, queries an hour or a mix of them, balance is measured as the standard deviation of the geoshards' scores, and neighbouring cells are added to a geoshard until it holds its share of the total. A dense metro ends up as several small geoshards, and a sparse region much larger than it shares one. The cells stay contiguous, so a search circle still falls into a few geoshards. The grouping is computed ahead of time, not per search, and is redone when the map of load shifts.

In this problem the dense metros are their own group, metro, because the simulation spreads a node's load evenly over its shards and cannot see one hot geoshard inside a group. The metros take 40% of the searches on well under 1% of the land. Equal-area thinking gives them one geoshard; load balancing gives them three of the seven.

Routing a search to its geoshards #

The geo router sits between the API and the index. For each search it covers the circle with S2 cells, looks up each cell's geoshard in a small map that every router instance keeps in memory, sends the search to those geoshards in parallel, and merges what comes back. Tinder's posts call this an abstraction layer; it also hides the geoshard layout, so the layout can change without touching the recommendation service.

A search near the middle of a large regional geoshard may read only one; one in a metro, where geoshards are small, reads several. Geoshards that are too small would make every search read many and hurt the P99 (the latency 99% of searches beat), which is why Tinder kept 40 to 100 worldwide; in their example a 100-mile search reads 3 of 55. The problem assumes about 3 per search. That is the whole gain: 3 geoshard searches instead of 7 shard searches, and each geoshard holds only nearby users, so each search scans less.

Replicas per geoshard #

A geoshard lives on a primary and its replicas. Replicas are full copies that answer searches for the geoshard and take over when a node dies. They also cost writes, since every copy applies every location change.

Replicas can follow load too: Tinder scales a hot geoshard by adding replicas, and spreads the primaries and replicas randomly over the data nodes (about four indexes per node), because geoshards in different time zones peak at different times, more than 10× apart in requests a second. One geoshard's evening peak in New York then shares a node with another's quiet night elsewhere. Here every geoshard gets three copies, so losing one leaves two to share its load.

Keeping the index in step with moves #

A location update has one job on the request path: save the location in profiles and answer. The index follows from a stream. The API publishes a change event; an indexer consumes it, computes the user's new cell and geoshard, and upserts the user there. A busy geoshard then slows only the indexer, never the app.

Moves are the interesting case. When the new cell belongs to another geoshard, the indexer must delete the user from the old geoshard and insert them into the new one: two writes on two indexes, not atomic. Two quick moves applied out of order could put the user back where they were, or in two geoshards at once. Keying the stream by user id puts all of one user's changes in one partition, read in order by one consumer; Tinder keys its Kafka partitions this way because one move can follow another within milliseconds (Passport, for example, lets a user set their location to another city). Failed writes are retried with exponential backoff and jitter, and refeeding from profiles repairs whatever still slips through.

Designing it step by step #

  1. The search path. Add the API and the geo router. The app calls the API, the API calls the router, and nothing on this path reads profiles.
  2. The geoshards. Add two Elasticsearch groups, metro and regional. Choose their shard counts so the metro group gets geoshards in proportion to its load, not its area, and give every geoshard at least two copies.
  3. The fan-out. In "Dense metro" the router searches 3 metro geoshards (x3), in "Elsewhere" 3 regional ones, and merges the candidates.
  4. The location update. The API writes profiles, publishes a change event to a Kafka topic keyed by user id, and answers.
  5. The indexer. Consume the stream and upsert the user in the geoshard that owns their cell; in "Moved geoshard", delete them from the old geoshard first.
  6. Size it. Count each group's searches and writes, divide by about 3k per node, and check each geoshard's copies stay well under 70% with one of them gone. The index is about two thirds of the budget.
  7. Explain the trade-offs in decision blocks: why location, why load and not area, why a router, why a stream.

Common mistakes #

In the interview #

Further reading #

Now design it

Review cards for this problem

Short questions on the ideas it needs, from the review cards. Review them daily so they stick.

More system design problems