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
Recommend: a user opens the app and asks for people within their radius. The request goes to a geo router (name it router) that covers the circle with S2 cells, maps them to geoshards, searches each one, filters by age and merges the candidates. Two scenarios, by where the searcher is:
"Dense metro": the circle lies in a dense metro; it covers 3 of the metro geoshards (name that group metro).
"Elsewhere": the circle lies anywhere else; it covers 3 of the regional geoshards (name that group regional).
Update location: the app reports where the user is. The location is saved in profiles before the app hears back, and a change event goes to a stream. The update never waits for the index.
Index location: an indexer consumes the change and updates the geoshard that owns the user's new S2 cell. Three scenarios:
"Dense metro": the user stays in a metro geoshard; one upsert there.
"Elsewhere": the user stays in a regional geoshard; one upsert there.
"Moved geoshard": the new cell belongs to another geoshard (in the model, a user arriving in a metro from elsewhere): delete the user from the old regional geoshard, then upsert them into the new metro one.
Use these ids, use case and scenario names exactly: the traffic, requirements and tests in problem.proschi refer to them.
Scale
6k searches a second at peak, 40% of them from dense metros that cover well under 1% of the land.
3k location updates a second, each indexed once; 5% of them move the user to another geoshard.
A search circle covers about 3 geoshards.
The searchable index needs at least 7 geoshards to hold it.
An Elasticsearch node serves about 3k requests a second.
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
Searches never read profiles, and no client connects to the index.
p99 of a search under 150 ms, of a location update under 80 ms.
Searches and location updates available 99.9% of the time.
Every geoshard has at least two copies; losing any single machine must not break a latency limit.
At most $13,500 / month, profiles included.
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
Skew inside one node. The simulation spreads a node's load evenly over its shards and replicas, so it cannot see one hot geoshard. The problem draws the dense metros as their own group, metro, so the cost of sizing geoshards by area instead of load shows up as that group's load.
Building the geoshards. Choosing the S2 level, scoring each cell's load and grouping cells into balanced geoshards is offline work done before any request. It is described in the lesson, not simulated.
Circles on a boundary. A search near the edge of a metro covers geoshards of both groups. The scenarios keep each search in one group.
Time zones. Each region peaks at its own local evening, and Tinder saw more than 10× difference in requests a second between geoshards. It spreads the primaries and replicas of the geoshards randomly over the data nodes, about four indexes per node, so the peaks even out; the simulation has one steady peak.
Consistency of a move. A delete and an upsert on two indexes are not atomic, and two quick moves can arrive out of order. Partitioning the stream by user id keeps one user's changes in order; the simulation has no reordering or crashes in the middle of a request.
Based on
The series lists Frank Ren, Xiaohu Li, Devin Thomson and Daniel Geng as authors.
Frank Ren, Geosharded Recommendations Part 1: Sharding Approach, Tinder Tech Blog, May 14, 2019: one Elasticsearch cluster and index with the default five shards, scaled with replicas and bigger nodes until CPU and cost were too high; searches capped at 100 miles; an equal latitude-longitude grid giving hot and empty shards; a load score per cell from unique users, active users or queries an hour, and balance measured as the standard deviation of the scores; Google's S2 cells (levels 7 and
grouped by load, so low-load geoshards are large and dense cities like New York and London small; 40 to 100 geoshards worldwide, since geoshards that are too small make each search read many and hurt the P99; a 100-mile search reading 3 of 55 geoshards in their example; a user crossing a boundary moved to the new index and removed from the old, not atomically; and a geosharded index handling 20× the computation of the single one.
Xiaohu Li, Geosharded Recommendations Part 2: Architecture, Tinder Tech Blog, May 29, 2019: an abstraction layer, an internal microservice, that works out the geoshards from the location and distance filter, queries them and aggregates; location changes going through the profile and location services, which decide on a shard move; one index per geoshard in one cluster rather than many clusters; replicas added to a hot geoshard; and primaries and replicas spread randomly over the data nodes, because geoshards in different time zones peak at different times.
Devin Thomson, Geosharded Recommendations Part 3: Consistency, Tinder Tech Blog, August 14, 2019: Kafka partitions keyed by document so one user's writes stay in order; a move done as a fetch of the document and an index into the new geoshard; retries with exponential backoff and jitter by asynchronous workers; and refeeding from the source of truth.
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.
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:
Recommend: the app asks the API, the API asks the geo router (router), and the router searches 3 geoshards. In "Dense metro" they belong to the metro group, in "Elsewhere" to the regional group.
Update location: the app's new location is written to profiles, a change event goes to a stream, and the app hears back.
Index location: an indexer consumes the event and upserts the user (insert, or update if already there) in the geoshard that owns their new cell; in "Moved geoshard" it first deletes them from the old one.
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.
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.
Flow
Rate
Where it lands
Recommend, dense metro
2.4k/s
7.2k geoshard searches/s on metro
Recommend, elsewhere
3.6k/s
10.8k geoshard searches/s on regional
Update location
3k/s
API, profiles (writes), the stream
Index location
3k/s
indexer; 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%.
"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.
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.
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.
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.
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.
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.
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.
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.
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.
The fan-out. In "Dense metro" the router searches 3 metro geoshards (x3), in "Elsewhere" 3 regional ones, and merges the candidates.
The location update. The API writes profiles, publishes a change event to a Kafka topic keyed by user id, and answers.
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.
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.
Explain the trade-offs in decision blocks: why location, why load and not area, why a router, why a stream.
Sharding by user id. Every search visits all 7 shards, each shard serves every search, and the index needs four copies of everything to keep up. It fails A search visits only the geoshards around the searcher and the budget.
Geoshards of equal area. The metros get one geoshard because they are small on the map. It takes 40% of the searches and saturates, so searches there slow past the limit. It fails p99 of Recommend < 150 ms.
Searching the profile database. The API scans profiles for a box of coordinates. It fails Searches go through the geo router: the source of truth is for writes, the index for searches.
Indexing inside the update. The API writes profiles, then deletes and inserts in the geoshards before it answers. The app waits for Elasticsearch, and a half-done move has nobody to retry it. It fails Location updates reach the geoshards through the stream and the update's latency limit.
Name the query first. "Everyone within R of a point, filtered" decides the shard key; say so before drawing shards.
Expect "what about New York?" That is the hot-spot question. Answer with load-balanced geoshards: smaller geoshards where users are dense, more copies where searches are heavy.
Expect "what if the radius is huge?" A wide circle covers more geoshards, so cap the radius (Tinder's limit is 100 miles) and keep geoshards large enough that a maximum-radius search still reads only a few. A remote area's geoshard is large anyway.
Expect "what happens when someone travels?" Delete from the old geoshard, insert into the new, in order per user through a keyed stream, with a background resync.
Expect "how do you rebalance?" Recompute cell scores, regroup cells into new geoshards, build the new indexes alongside the old ones and switch the router's map once they have caught up.
Martin Kleppmann, Designing Data-Intensive Applications, chapter 6, "Partitioning" (the sections on partitioning secondary indexes and skewed workloads).