Understand the Problem
Tinder is a mobile dating app that helps people connect by allowing users to swipe right to like or swipe left to dislike on profiles. It uses location data and use-specified preferences to suggest potential matches nearby.
Functional Requirements
- Users can create a profile with preferences
- Users can view a stack of potential matches in line with their preferences and within maximum distance of their current location.
- Users can swipe right to match and swipe left to pass on a profile.
- Users get a match notification when they both swipe right on each other.
Non-Functional Requirements
- The system should be strong consistency for swiping.
- The system should be able to scale horizontally for a large number of users. Scale to lots of daily users / concurrent users.
- The system should load potential matches stack with low latency.
- The system should avoid showing user profiles that the user previously swiped left on.
Capacity Estimation
- Assume 10 million daily active users
- Assume 100 potential matches per user
10M * 100 / 100K= 10k writes per second High Peek: 10k * 2 = 20k writes per second
Read-write ratio: 1:20
- Assume 1 million daily active users
- Assume 100 potential matches per user
1M * 100 / 100K = 1k writes per second High Peek: 1k * 2 = 2k writes per second
Core Entities
- User: Contains user information, such as name,
- Swipe: Expression of yes or no on a user profile. swiping_user and target_user are foreign keys to the User table.
- Match: A connection between 2 users as a result of them both swiping right on each other.
API or System interface
The API is the primary interface that users will interact with. We should define the API early on, as it will guide your high-level design. We just need to define an endpoint for each of our functional requirements.
The first endpoint we need to define is an endpoint to create a user profile.
POST /profile
{
name: 'Alice',
ageMin: 20,
ageMax: 30,
gender: 'female',
distance: 10
....
}Next we need an endpoint to get the feed of user profiles to swipe on.
GET /feed?lat={}&long={}&distance={} -> User[]We also need an endpoint to power swiping:
POST /swipe/{userId}
{
direction: 'left' | 'right'
}Finally, we need an endpoint to get a list of matches:
GET /matches -> Match[]High Level Design
We'll start our design by going one-by-one through our functional requirements and design single system to satisfy them. One we have this in place, we'll layer on depth via our deep drives.
Users can create a profile with preferences and specify a maximum distance.
The first thing we need to do is in a dating app like Tinder is allow users to tell us about their preferences. This way we can increase the probability of them finding love by only showing them profiles that match their preferences.
We'll need to take the post request to POSt /profile and persist these settings in a database.
- The client sends a POST request to /profile with the profile information as the request body.
- The API Gateway routes this request to the Porfile service.
- The Profile service update the user's profile preferences in the database.
- The Profile service responds to the client with a success message.
Users can view a stack of potential matches
When a user enters the app, they will immediately served a stack of profiles to swipe on. These profiles abide by filters that the user specified as well as the user's location.
Serving up the feed efficiently is going to be a key of challenge of the system, but we'll start simple and optimize later during the deep dive.
The easiest thing we can do it just query the database for a list of users that match the user's preferences andreturn them to the client. We'll need to also consider the users current location as to make sure they only get serves profiles close to them.
Users can swipe right / left on profiles one-by-one
Once users have their "stack" of profiles they're ready to find love! They just need to swipe right if they like the person and left if they don't. The system needs to record each swipe and tell the user that they have a match if anyone they swipe right on has previously swiped right on them.
We need a way to persist swipes and check if they're a match. Again, we'll start with something simple and inefficient and improve upon it during our deep dives.
Given that the swipe interaction is so effortless, we can assume we're going to get a lot of writes to the DB. Additionally, there is going to be a lot of swipe data. If we assume 20M daily active users doing 200 swipes a day on average, that nets us 4B swipes a day. This certainly means we'll need to partition the data.
Cassandra is a good fit as a database here. We can partition by swiping_user_id. This means an access pattern to see if user A swiped on user B will be fast, because we can predictably query a single partition for that data. Additionally, Cassandra is extremely capable of massive writes, due to its write-optimized storage engine (CommitLog + Memtables + SSTables). A con of using Cassandra here is the element of eventual consistency of swipe data we inherit from using it. We'll discuss ways to avoid this con in later deep dives.
When a user swipes:
- The client sends a POST request to /swipe with the profile ID and the swipe direction (right or left) as parameters.
- The API Gateway routes this request to the Swipe Service.
- The Swipe Service updates the Swipe Database with the swipe data.
- The Swipe Service checks if there is an inverse swipe in the Swipe Database and, if so, returns a match to the client.
Users get a match notification if they mutually swipe on each other
When a match occurs, both people need to be notified that there is a match. To make things clear, let's call the first person who like the other Person A. The second person will be called Person B.
Notifying Person B is easy! In fact, we've already done it. Since they're the second person to swipe, immediately after they swipe right, we check to see if Person A also liked them and, if they did, we show a "You matched!" graphic on Person B's device.
But what about Person A? They might have swiped on Person B weeks ago. We need to send them a push notification informing them that they have a new connection waiting for them.
To do this, we're just going to rely on device native push notifications like Apple Push Notification Service (APNS) or Firebase Cloud Messaging (FCM).
Let's quickly recap the full swipe process again, now that we've introduced push notifications into the flow.
- Some time in the past, Person A swiped right on Person B and we persisted this swipe in our Swipe DB.
- Person B swipes right on Person A.
- The server checks for an inverse swipe and finds that it does, indeed, exist.
- We display a "You Matched!" message to Person B immediately after swiping.
- We send a push notification via APNS or FCM to Person A informing them that they have a new match.
Potential Deep Dives
1. How can we ensure that swiping is consistent and low latency?
Let's start by considering the failure scenario. Imagine Person A and Person B both swipe right (like) on each other at roughly the same time. Our order of operations could feasibly look something like this:
- Person A swipe hits the server and we check for inverse swipe. Nothing.
- Person B swipe hits the server and we check for inverse swipe. Nothing.
- We save Person A swipe on Person B.
- We save Person B swipe on Person A.
Now, we've saved the swipe to our database, but we've lost the opportunity to notify Person A and Person B that they have a new match. They will both go on forever not knowing that they matched and true love may never be discovered.
Good Solution:
Approach
An effective method to achieve both consistency and low latency is to utilize Redis for atomic swipe processing. Redis is an in-memory data store known for its speed and support for atomic operations. By leveraging Redis's atomic commands or Lua scripting, we can process swipes and check for reciprocal likes in a single, indivisible operation.
When a user swipes right, we perform an atomic operation that simultaneously records the swipe and checks if the other user has already swiped right on them. This can be done using Redis data structures like sets or hashes. For example, we can store each user's likes in a set and use the SISMEMBER command to check for a reciprocal swipe.
The in-memory nature of Redis ensures that these operations are executed with minimal latency, providing users with immediate feedback. Redis's single-threaded architecture guarantees that operations are executed atomically without the need for explicit locking mechanisms, further enhancing performance and consistency.
This way, be are both consistent and low latency.
Challenges
This is not without its challenges. While Redis offers significant speed advantages, it also presents some challenges. Since Redis stores data in memory, there is a risk of data loss in the event of a system crash or power failure unless persistence features like snapshots or Append Only Files (AOF) are enabled. However, enabling persistence can introduce additional overhead and complexity.
Managing memory usage becomes critical as the number of users and swipes increases. We need to implement strategies for data eviction or periodically offload less frequently accessed data to a persistent storage system to prevent memory exhaustion.
Ensuring data consistency across multiple Redis nodes in a clustered environment can be complex. Network partitions or node failures can lead to inconsistencies if not handled properly. Additionally, Redis does not support multi-key atomic operations across shards, which may require careful data partitioning to maintain atomicity.
2. How can we ensure low latency for feed/stack generation?
When a user open the app, they want to immediately start swiping. They don't want to have to wait for us to generate a feed for them.
Good Solution: Use of indexed database for Real-Time Query
Approach
One method to achieve low latency is by utilizing indexed databases for real-time querying. By creating indexes on the fields most commonly used in feed generation—such as user preferences, age range, and especially geospatial data like location—we can significantly speed up query response times. Implementing a geospatial index allows the system to efficiently retrieve users within a specific geographic area.
To handle the scale and performance requirements of an application like Tinder, a search-optimized database such as Elasticsearch or OpenSearch can be employed. These databases are designed for fast, full-text search and complex querying, making them suitable for handling large volumes of data with minimal latency.
By leveraging the powerful indexing and querying capabilities of these databases, we can generate user feeds in real-time while keeping response times low. This approach ensures that users receive up-to-date matches that align closely with their current preferences and location.
Challenges
The main challenge here is maintaining data consistency between the primary transactional database and the indexed search database can be complex. Any delay or failure in synchronizing data updates may result in users seeing outdated profiles or missing out on new potential matches.
This can be solved via change data capture (CDC) mechanisms that keep the indexed database in sync with the primary transactional database. Depending on the rate of updates, we may want to use a batching strategy to reduce the number of writes to the indexed database, since Elasticsearch is optimized for read-heavy workloads, not write-heavy workloads.
Good Solution: Pre-generate and cache feed
Approach
Another strategy is to pre-compute and cache user feeds asynchronously. Periodic background jobs can generate feeds based on users’ preferences and locations, storing them in a cache for instant retrieval when the user opens the app. This ensures that the feed is readily available without the need for real-time computation.
By serving these cached feeds, users experience immediate access to potential matches, enhancing their satisfaction. The pre-computation can be scheduled during off-peak hours to reduce the impact on system resources, and frequent updates ensure that the feeds remain relevant.
Challenges
The primary challenge with this approach is that highly active users may quickly exhaust their cached feeds, leading to delays while new matches are generated or fetched. Additionally, pre-computed feeds may not reflect the most recent changes in user profiles, preferences, or the addition of new users to the platform. This could result in less relevant matches and a diminished user experience.
What's worse is that if the user swipes through their pre-computed cached stack, we need to run the expensive query again to load new matches for them, which would be inefficient and slow.
3. How can the system avoid showing user profiles that the user has previously swiped on?
Good Solution: Client-Side Cache + DB Query + Contains Check
Approach
Building off the previous approach, we might consider doing contains queries on the backend and adding a cache that houses recent user swipes to avoid the problems presented with an availability-skewing system. However, we wouldn't manage this cache on the backend. We'd manage it client-side.
Managing a cache on the backend merely to store data before it "lands" on all partitions in a NoSQL system would be expensive. We can take advantage of the fact that the client is part of the system and have the client store recent swipe data (perhaps the K most recent swipes). This will allow the client to filter out profiles that might be suggested in a feed that have already been swiped on recently.
This cache is doubly useful in the situation where a user is close to depleting their initial stack of profiles while swiping. Imagine a user swiping through 200 pre-fetched profiles. When the user gets to profile ~150, the client can:
- Ping the backend to generate a new feed for the user.
- Request that feed once the backend is done generating the feed.
- Filter out any profiles that the user eventually swipes on.
The client works as a part of this system because we can make the assumption that the user is only using this app on one device. Therefore, we can leverage the client as a place to manage and store data.
Challenges This solution is still subjected to the problems created by users with extensive swipe histories and large user ID contains checks that get slower as the user swipes more.