Design a Geo-Based Matching Service
TL;DR
Build a system that serves recommendation stacks of nearby users, filtering by already-swiped, preferences, and distance -- all within 200ms. The core insight is that naive lat/lng range queries are unusably slow at scale; you need geospatial indexing with S2 geometry cells to partition users into cells and query only nearby cells. Tinder processes 1.6 billion swipes per day across 75 million monthly active users. The real engineering challenge is not the matching algorithm -- it is generating a personalized stack of 200 candidates from millions of nearby users without scanning the entire user base. Bloom filters to deduplicate already-swiped users. Elo-style scoring to rank attractiveness. Geosharding to colocate geographically proximate users on the same database shard for 20x query performance.
The System
Think Tinder. A user opens the app. They see a stack of profiles -- people near them, matching their preferences (age range, gender, distance). They swipe right (like) or left (pass). If two users both swipe right, it is a match. The app must generate this stack in real time, personalized to each user, and never show someone they have already swiped on.
Why is this hard? Because "find nearby users I have not swiped on who match my preferences" sounds like a database query, but it is actually a recommendation problem at massive scale. A user in Manhattan might have 500,000 potential matches within 15 miles. You cannot rank all 500K on every app open. You need to precompute candidate pools, index them geospatially, filter them cheaply, and rank them fast. Tinder reportedly regenerates recommendation stacks every time the user changes location by more than 1 mile, which at peak hours means millions of stack generations per minute.
Requirements
Functional Requirements
| Requirement | Details |
|---|---|
| Profile creation | Users create profiles with photos, bio, age, gender, preferences. |
| Location update | App sends GPS coordinates when opened and periodically during use. |
| Recommendation stack | Generate a stack of ~200 candidate profiles ranked by compatibility. |
| Swipe action | Record like/pass. Never show the same profile twice. |
| Match detection | When both users like each other, create a match and notify both. |
| Filters | Distance radius (1-100 miles), age range, gender preference. |
Non-Functional Requirements
| Requirement | Target |
|---|---|
| Stack generation latency | < 500 ms (first stack), < 200 ms (subsequent) |
| Swipe recording latency | < 100 ms |
| Match notification latency | < 2 seconds |
| Availability | 99.9% |
| Scale | 75M MAU, 15M DAU, 1.6B swipes/day, peak 50K swipes/sec |
Back-of-Envelope Math
Daily active users: 15M
App opens per user/day: ~7 (Tinder's reported average session count)
Stack generation events: 15M * 7 = 105M/day = ~1,200/sec avg, ~3,600/sec peak
Swipes per day: 1.6B
Swipes per second: 1.6B / 86400 = ~18,500 avg, ~50,000 peak
Right-swipe rate: ~25% (industry average)
Right-swipes per day: 1.6B * 0.25 = 400M
Match rate: ~3% of right-swipes are reciprocated (historical)
Matches per day: 400M * 0.03 / 2 (avoid double-counting) = ~6M
Location updates/day: 15M users * 10 updates/day = 150M
Location storage: Each record = (user_id: 8B, lat: 8B, lng: 8B, timestamp: 8B) = 32 bytes
Active user location data: 15M * 32 bytes = 480 MB (fits in RAM easily)
Swipe history:
Avg swipes/user (lifetime): ~50,000 (power users much higher)
Total swipe records: 75M * 50K = 3.75 trillion
Per-user Bloom filter: 50K items, 0.1% FPR = ~90 KB per user
Total Bloom filter memory: 15M DAU * 90 KB = ~1.35 TB
That Bloom filter number is the first surprise. 1.35 TB just for "have I already swiped on this person?" tracking. This is why you cannot use a simple HashSet -- the swipe history is too large for naive in-memory storage, but Bloom filters compress it 100x.
Naive Design
Start with PostgreSQL and PostGIS.
Components:
- Users table:
(user_id, lat, lng, age, gender, preferences, last_active). - Swipes table:
(swiper_id, swipee_id, direction, timestamp). - Matches table:
(user_a, user_b, timestamp).
Stack generation query:
SELECT * FROM users
WHERE ST_DWithin(
geography(ST_MakePoint(lng, lat)),
geography(ST_MakePoint(:my_lng, :my_lat)),
:radius_meters
)
AND gender = :preferred_gender
AND age BETWEEN :min_age AND :max_age
AND user_id NOT IN (SELECT swipee_id FROM swipes WHERE swiper_id = :me)
ORDER BY ST_Distance(...) ASC
LIMIT 200;
Swipe recording:
INSERT INTO swipes (swiper_id, swipee_id, direction) VALUES (:me, :them, 'right');
-- Check for mutual match
SELECT 1 FROM swipes WHERE swiper_id = :them AND swipee_id = :me AND direction = 'right';
This works for 10,000 users. It absolutely does not work for 15 million daily active users.
Where It Breaks
Problem 1: The NOT IN Subquery is a Death Sentence
NOT IN (SELECT swipee_id FROM swipes WHERE swiper_id = :me) scans 50,000+ rows per user on every stack generation. At 1,200 stack generations per second, that is 60 million row scans per second just for deduplication. PostgreSQL will fall over.
Problem 2: Spatial Range Queries on Flat Indexes Are Slow
ST_DWithin with a B-tree index still has to scan a bounding box and then filter by actual distance. In dense areas (Manhattan, Mumbai), the bounding box for 15 miles might contain 500,000 users. Scanning all of them per request is O(N) where N is the local population density.
Problem 3: Location Updates Create Write Storms
150 million location updates per day = 1,700/sec. Each update changes the user's lat/lng, which invalidates spatial indexes. On a single PostgreSQL instance, this is constant index rebuilding.
Problem 4: No Ranking Beyond Distance
Sorting by distance alone produces terrible recommendations. A user 1 mile away who has been inactive for 3 months should not rank above an active user 5 miles away. You need an attractiveness score, activity recency, and profile completeness signal.
Problem 5: Match Detection Requires Global State
Checking "did they already swipe right on me?" requires querying the swipes table for the other user. At 50K swipes/sec, this doubles the swipe write path to include a read-before-write pattern. Under contention, this serializes.
Real Design
Architecture Overview
┌──────────────┐
│ API Gateway │
└──────┬───────┘
│
┌──────────────┼──────────────┐
│ │ │
┌────────┴───┐ ┌──────┴──────┐ ┌────┴────────┐
│ Location │ │ Stack │ │ Swipe │
│ Service │ │ Generator │ │ Service │
└────────┬───┘ └──────┬──────┘ └────┬────────┘
│ │ │
┌────────┴───┐ ┌──────┴──────┐ ┌────┴────────┐
│ Geo Index │ │ Candidate │ │ Bloom │
│ (S2 Cells) │ │ Pool Cache │ │ Filter │
│ (Redis) │ │ (Redis) │ │ Store │
└────────────┘ └─────────────┘ └─────────────┘
│
┌───────┴───────┐
│ User DB │
│ (sharded by │
│ S2 cell) │
└───────────────┘
Component 1: Geospatial Indexing with S2 Geometry
S2 geometry, developed by Google, maps the Earth's surface onto a unit sphere and then onto six faces of a cube, which are recursively subdivided into cells at 30 levels of precision. Each cell has a unique 64-bit ID. Why S2 and not geohashing?
Geohash problems:
- Geohash cells are rectangles on a Mercator projection. Near the poles, they are wildly distorted.
- Two points near each other can have completely different geohash prefixes if they straddle a cell boundary. The classic "edge problem."
- Covering a circle (distance radius) with geohash rectangles produces many edge cells that overlap.
S2 advantages:
- Cells are roughly equal area at every level. No polar distortion.
- Covering a circle with S2 cells produces a tight set of cells with minimal waste.
- S2 cells are hierarchical: a level-12 cell (3.31 km^2) contains 4 level-13 cells. You can query at coarse granularity in sparse areas and fine granularity in dense areas.
How it works for matching:
- Each user's location is mapped to an S2 cell at level 12 (roughly 1.8 km x 1.8 km).
- Users are stored in Redis sorted sets keyed by S2 cell ID:
cell:{s2_cell_id}-> sorted set of user IDs scored by last_active timestamp. - To find candidates within 15 miles: compute the S2 covering for a circle of radius 15 miles centered on the user. This returns ~50-200 S2 cell IDs.
- Query those cell IDs in Redis. Union the results. You have your raw candidate pool.
Performance: Instead of scanning 500K users in a bounding box, you query ~100 Redis keys and union them. Each key lookup is O(log N) where N is users per cell. Total: ~100 * O(log 1000) = negligible. This is the 20x performance improvement over naive spatial queries.
Component 2: Bloom Filters for Already-Swiped Deduplication
You absolutely cannot run a NOT IN query against 50,000 swipe records on every stack generation. Bloom filters solve this.
Setup: Each active user gets a Bloom filter that contains all user IDs they have ever swiped on.
Bloom filter parameters:
Expected items: 50,000 (lifetime swipes)
False positive rate: 0.1%
Bits needed: 50,000 * 14.4 = 720,000 bits = 90 KB per user
Hash functions: 10 (optimal for this FPR)
Usage: When generating a stack, for each candidate from the geo index, check the Bloom filter. If the filter says "probably seen," skip that candidate. If it says "definitely not seen," include them.
False positives: A 0.1% false positive rate means 1 in 1,000 candidates is wrongly skipped. On a stack of 200, that is 0.2 candidates lost. Acceptable -- the user never knows they missed one person.
False negatives: Bloom filters have zero false negatives. A user will NEVER see someone they already swiped on. This is the critical correctness guarantee.
Storage: 15M DAU * 90 KB = 1.35 TB of Bloom filter data. Store in Redis or a dedicated in-memory store. Persist to disk for recovery. Rebuild from the swipes table on cold start (takes ~30 min for the full dataset).
Component 3: Elo-Style Attractiveness Scoring
Tinder's original ranking system used an Elo rating, borrowed from chess. The idea: if a high-rated user swipes right on you, your rating increases more than if a low-rated user does. Conversely, a left-swipe from a high-rated user hurts more.
Simplified scoring:
After user A (rating Ra) swipes on user B (rating Rb):
Expected outcome: E = 1 / (1 + 10^((Rb - Ra) / 400))
If right-swipe: B's new rating = Rb + K * (1 - E)
If left-swipe: B's new rating = Rb + K * (0 - E)
K = 32 (standard chess K-factor)
Tinder publicly replaced Elo with a more opaque system in 2019, but the principle remains: there is a scoring function that ranks users, and it is continuously updated based on swipe behavior.
Why Elo matters for system design: It means the ranking is not just based on distance and preferences. The stack generator must incorporate a pre-computed attractiveness score, activity recency, and profile quality into a composite ranking. This score is stored per-user and updated asynchronously as swipes come in.
Component 4: Stack Generation Pipeline
This is the critical path. When a user opens the app:
Step 1: Geo query (10-50 ms) Query S2 cell index for all users within the configured distance radius. Returns ~5,000-50,000 raw candidates depending on density.
Step 2: Preference filter (5-10 ms) Filter by gender, age range. Typically removes 50-70% of candidates.
Step 3: Bloom filter dedup (10-20 ms) Check each remaining candidate against the user's Bloom filter. Removes already-swiped users. In a mature user's case, this might remove 80%+ of candidates.
Step 4: Score and rank (20-50 ms) For remaining candidates (~200-2000), compute a composite score:
score = w1 * elo_score
+ w2 * distance_decay(distance)
+ w3 * activity_recency(last_active)
+ w4 * profile_completeness
+ w5 * mutual_friend_count (if available)
Sort by score. Take top 200.
Step 5: Hydrate profiles (30-50 ms) Fetch full profile data (photos, bio) for the top 200 from the user database. Cache-friendly because these are popular profiles.
Total: ~75-180 ms. Well within the 200ms target for subsequent stacks.
Pre-computation: For the first stack (cold start), this might take 500ms. To meet the 500ms target, pre-compute candidate pools for active users during off-peak hours. When a user opens the app, serve the pre-computed stack and regenerate asynchronously for their updated location.
Component 5: Swipe Recording and Match Detection
Swipes must be recorded durably and match detection must be atomic.
Write path:
- User swipes right on candidate.
- Swipe service writes to Kafka topic
swipeswith(swiper_id, swipee_id, direction, timestamp). - Consumer writes to the swipes database (sharded by swiper_id).
- Consumer updates the swiper's Bloom filter (add swipee_id).
- Consumer checks for mutual match: look up
(swipee_id -> swiper_id, direction=right)in the swipes database. - If mutual match found, write to matches table and push notifications to both users.
Why Kafka here? Because swipe volume is 50K/sec at peak. Direct database writes at this rate require careful connection pooling and batching. Kafka absorbs the burst, and consumers process at a steady rate with back-pressure.
Match detection race condition: What if user A and user B swipe right on each other simultaneously? Both consumers check for a mutual match, both find it, both create a match record. You get a duplicate match. Solution: use a deterministic match ID: match_id = hash(min(user_a, user_b), max(user_a, user_b)). Insert with ON CONFLICT DO NOTHING. Idempotent.
Component 6: Geosharding the User Database
The user database is sharded by S2 cell at a coarse level (level 5, roughly 250km x 250km regions).
Why geoshard? A stack generation query needs users from nearby cells. If nearby users are on the same shard, the query hits one database node instead of scattering across many. This is the opposite of random hash sharding -- you deliberately colocate geographically proximate users.
Rebalancing problem: New York has 500x more users than rural Wyoming. Geoshards are inherently unbalanced. Solution: use virtual shards. Dense areas are split into sub-shards at finer S2 levels. Sparse areas share a shard. The routing layer maps S2 cell ID to physical shard, and this mapping is updated monthly based on density.
Cross-shard queries: A user in New Jersey searching within 30 miles will need users from both the New Jersey shard and the New York shard. The stack generator issues parallel queries to both shards and merges results. This is the same scatter-gather pattern as search engines.
Deep Dives
Deep Dive 1: Adaptive S2 Cell Levels for Density Variation
The fixed level-12 S2 cell approach has a problem. In Manhattan, a level-12 cell (3.31 km^2) might contain 50,000 users. In rural Kansas, it might contain 3. You do not want the same granularity everywhere.
Solution: Adaptive cell levels based on user density.
If cell contains < 100 users: use level 10 (212 km^2, merge up)
If cell contains 100-10,000: use level 12 (3.31 km^2, standard)
If cell contains > 10,000: use level 14 (0.21 km^2, split down)
The geo index stores users at the appropriate level. When covering a radius, the covering algorithm automatically generates cells at mixed levels -- large cells in sparse areas, small cells in dense areas. This keeps every cell at a manageable size (100-10,000 users) regardless of local population density.
Tinder's actual approach: Tinder reportedly uses a combination of geohashing and custom spatial indexing. Bumble uses H3 (Uber's hexagonal grid system). The specific system matters less than the principle: adaptive granularity based on density.
Deep Dive 2: Recommendation Stack Quality
Distance plus Elo produces functional but boring recommendations. Real dating apps use multi-armed bandit exploration.
The explore/exploit tradeoff: If you always show the highest-scored candidates first, users see the same type of person repeatedly. They get bored, swipe less, and churn. You need to inject diversity.
Thompson sampling approach:
For each candidate:
observed_right_swipe_rate = right_swipes / total_swipes
sample from Beta(right_swipes + 1, left_swipes + 1)
Use the sample as the candidate's score
This naturally explores less-seen profiles (high variance in the Beta distribution) while exploiting known-good profiles (low variance). New users get more exposure because their Beta distribution is wide.
Practical implementation: The stack generator computes deterministic scores for 80% of the stack (top candidates by composite score) and uses Thompson sampling for the remaining 20% (exploration slots). This balances user satisfaction with new-user visibility.
Deep Dive 3: Location Privacy and Update Throttling
Storing exact GPS coordinates and sharing precise distances is a privacy nightmare. Bumble was criticized for leaking exact user locations through distance trilateration -- an attacker creates three accounts, measures the reported distance from each, and triangulates the target.
Mitigations:
- Snap to grid: Round coordinates to the nearest 0.01 degrees (~1.1 km). Store the snapped location, not the exact one. Distance shown as "< 1 mile" or "2 miles away."
- Randomized offset: Add a random offset of 100-500 meters to each stored location. The offset is deterministic per user (seeded by user_id) so it does not jitter between sessions.
- Location update throttling: Do not accept updates more than once per 5 minutes. This limits the resolution of movement tracking.
- Hide distance for very close users: If distance < 1 mile, just show "< 1 mile." Do not show "0.2 miles" -- that is apartment-level precision.
System design impact: Snapping to grid means your S2 cell assignments might be off by one cell. You must always query neighboring cells as well (the S2 library provides GetAllNeighbors() for this). The 200-meter error is invisible in a 15-mile search radius but matters for "1 mile" searches -- overfetch and re-sort.
Alternative Designs
| Approach | Pros | Cons | When to Use |
|---|---|---|---|
| S2 cells + Redis (described above) | 20x faster than spatial DB queries. Adaptive granularity. | Requires custom geo index maintenance. Redis memory costs. | High-density areas, 10M+ users, Tinder/Bumble scale |
| PostGIS with R-tree | Built-in spatial indexing. ACID transactions. Simple. | O(N) scan in dense areas. Cannot handle 50K swipes/sec writes. | < 1M users, MVP, hackathon |
| Elasticsearch geo queries | Geoshape queries, distance sorting, aggregations built in. Good for 1-10M users. | Write latency for near-real-time location updates. Not designed for high-write workloads. | Medium scale, location + text search combined |
| H3 hexagonal grid (Uber) | Equal-area hexagons, no edge effects, ring queries built in. | Less mature than S2. Fewer language bindings. | When hex grids suit the use case (delivery, ride-sharing) |
| Quadtree in memory | Excellent for non-uniform density. Adaptive by nature. | Custom implementation. Hard to distribute across nodes. | Single-region, in-process spatial index |
Scaling Math Verification
Geo Index Sizing
Daily active users: 15M
S2 level-12 cells on Earth: ~7.3 million
Avg users per active cell: 15M / ~200K active cells = ~75 users/cell
Redis memory per cell: sorted set with 75 members * (8B user_id + 8B score) = 1.2 KB
Total geo index: 200K cells * 1.2 KB = 240 MB
With adaptive levels: ~500 MB total (more cells in dense areas)
Conclusion: Entire geo index fits in a single Redis instance. Replicate 3x for reads.
Swipe Processing
Peak swipes/sec: 50,000
Kafka partitions: 50 (1,000 swipes/sec per partition -- comfortable)
Bloom filter update rate: 50,000 updates/sec
Each update: 10 hash computations * 50 ns = 500 ns per update
Total CPU for Bloom updates: 50,000 * 500 ns = 25 ms/sec (one core handles this)
Match check: 50,000 * 0.25 (right-swipes only) = 12,500 lookups/sec
Each lookup: 1 Redis GET or DB point query = ~1 ms
12,500 * 1 ms = 12.5 seconds of serial work -> parallelize across 15 consumers
Stack Generation
Peak stack generations/sec: 3,600
Per generation:
S2 cell queries (Redis SMEMBERS): 100 cells * 0.2 ms = 20 ms
Bloom filter checks (2000 candidates): 2000 * 0.5 us = 1 ms
Scoring (500 candidates): 500 * 0.01 ms = 5 ms
Profile hydration (200 profiles): batch GET from cache = 10 ms
Total per request: ~36 ms
Total CPU: 3,600 * 36 ms = 130 seconds/sec -> 130 cores at peak
Server count: 130 / 8 cores = ~17 servers for stack generation
Failure Analysis
| Failure | Impact | Mitigation |
|---|---|---|
| Redis geo index goes down | Cannot generate new stacks. Users see stale stack from client cache. | 3x Redis replicas with automatic failover (Redis Sentinel). Client caches last stack locally -- serves stale for up to 30 min. |
| Bloom filter store lost | Users might see profiles they already swiped on. Embarrassing but not catastrophic. | Rebuild from swipes database. Takes ~30 min for full rebuild. During rebuild, fall back to database query for dedup (slower but correct). |
| Kafka swipe pipeline lag | Match notifications delayed. Bloom filters not updated (users see already-swiped profiles temporarily). | Monitor consumer lag. Alert on > 60 seconds lag. Auto-scale consumers. Swipe recording is idempotent, so replay is safe. |
| User database shard goes down | Users on that shard cannot be recommended or load their profiles. | Standard database replication. Read replicas serve stack generation. Primary failover via orchestrator. |
| Elo score computation stalls | Ranking degrades to distance-only. Stack quality drops. | Elo computation is asynchronous. Cached scores remain valid for days. Alert on update staleness. |
| Location service overloaded | Users appear at stale locations. Stack may show users who have moved away. | Location staleness is tolerable for minutes. Degrade gracefully -- serve last known location. Rate limit updates to 1 per 5 min anyway. |
| Dense area overwhelms stack generator | Stack generation takes > 500ms in Manhattan. | Adaptive S2 levels cap candidate pool per cell. Pre-compute stacks for dense areas during off-peak. Add more stack generator instances. |
Level Expectations
| Level | What the Interviewer Expects |
|---|---|
| Mid (L4) | PostGIS or geohash approach. Swipes table with NOT IN. Knows it does not scale. Proposes sharding but hand-waves on how. Mentions caching profiles. Sorts by distance only. |
| Senior (L5) | S2 or H3 geospatial indexing. Bloom filters for dedup (with FPR math). Composite scoring beyond distance. Kafka for swipe ingestion. Geosharding with density awareness. Quantified back-of-envelope math. Match detection with idempotency. |
| Staff+ (L6) | Adaptive S2 cell levels based on density. Thompson sampling for explore/exploit in recommendations. Location privacy analysis (trilateration attack, grid snapping). Pre-computed stack generation for cold start optimization. Detailed failure analysis for each component. Reference to Tinder/Bumble/Hinge actual architectures. Discussion of Elo replacement and its system design implications. |
References from Our Courses
- Spatial Indexing — geohash and H3 for location-based candidate matching
- Redis Data Structures and Use Cases — caching active user locations for fast lookups
- Bloom Filters — filtering already-shown profiles efficiently
Red Team This Design
Ready to stress-test this architecture? The Attack companion tears apart every decision in this design — from hardware physics to security holes to what actually happens at 10x scale.