Beli System Design

What is Beli?

I use Beli from time to time to log restaurants I've been to, as well as mark down restaurants I plan to go to. As a social media app, Beli is where I can see my friends doing the same and either get inspired or get... surprised... by their taste.

It has a number of features, but here I'll just go over the functionality that I plan to map out in this post. I'll design how they work, from high level overviews to low level implementations, all of which, by the way, I'm entirely making up as I go. All I'm armed with is my past experience building software products and my time as a user of the app. Let's start!

Functional and non-functional requirements

First, functional requirements. What do we want Beli to do: what specific features should we map out, what user actions should be possible? I'll brainstorm a list:

• Users can authenticate
• Users can follow other users
• Users can view a list of users they follow, and a list of users who follow them
• Users can set their account to private to limit visibility of their activity to just their followers.
• Users can search for restaurants.
• Users can view restaurant details
• Users can review restaurants by ranking them relative to others they have visited to produce a score, and adding photos and notes.
• Users can view the reviews made by a user according to the latter user's privacy settings
• Users can receive notifications

Now for nonfunctional requirements; what are the attributes and constraints of my system?

• Scalability to support millions of users
• High availability > consistency: like most user-facing apps, we want high availability, which can come at the cost of no strong consistency, but eventual consistency is still totally fine. For example, it's alright if it takes a bit of time for a friend's added restaurant to show up on a user's feed, but it's not fine if the user's feed is unaccessible whenever a friend adds a restaurant to their list.
• Remain available under unusually high traffic
• Durability: once user data is confirmed as saved, it is not lost
• Performance: low latency for all user-facing operations

For those familiar with the app, and for the sake of completeness, here's an explicit (yet likely non-exhaustive) list of what I'm considering out of scope for the sake of this post: OpenTable integration and reservations, challenges and streaks, Want to Try list, taste profile, guides, leaderboard, trending, categories of restaurants.

Entities and API design

Before designing some core APIs, I'd like to delineate the core entities in the system. That way, I can define my APIs around the relationships between the entities. It will also guide my data modelling down the line.

• User
• Follow
• Restaurant
• Review
• Photo
• Notification

Now for the APIs. Here's where the fun starts. I'll go through my list of functional requirements one by one and write at least one API route for each. I'll follow REST semantics.

Firstly, authentication. We can handle this with Json web tokens (JWTs). This means that authenticated requests will have a header Authorization: Bearer <jwt>. I choose this over different authentication methods, such as sessions, because JWTs are stateless, which is much more compatible with horizontally scaled servers, something I'll need for the large scale this system is intended to handle. I'll make sure to configure the JWTs to have short expiry time in case they get intercepted, and I'll have the server send longer-lived refresh tokens to users to make up for that.

As for authentication routes: users should be able to register a new account, login to an existing account, and logout of an account. All are POST requests so we can put sensitive info, such as a password, in the request body (not the unsecure URL string itself), to prevent malicious/unintended caching, and because they affect auth state. For example, the refresh endpoint triggers the server to talk to some auth database to rotate the refresh token and issue a new JWT.

• POST /auth/register
• POST /auth/login
• POST /auth/refresh
• POST /auth/logout

To check how Beli handles authentication, I logged out on my app then tried to log back in. Then I realize I've forgotten my password since I've never logged out before. Oops.

Next up is the crux of a social media app: users should be able to follow other users. In technical terms, this means a user calling an API endpoint to create a follow for another user, which can be uniquely identified with a userId.

• POST /follows/{userId}

Note that we don't need to include the user's own userId in the URL string since the server can determine identity of the API request caller using the JWT in the Authorization header of the request, as mentioned above.

Users also want to query lists of followers/following. By default we can just retrieve all of them, though if someone has many, many followers, for example, we'd want to add a query parameter for paginating the results. Probably. I'm not sure what Beli does in production, because, of course, I do not have enough followers to warrant pagination...

• GET /follows/followers
• GET /follows/following

Unfortunately for the users of this theoretical system, I neglected to add unfollowing as a functional requirement. Just to show these theoretical users exactly what they're missing out on, I'll write the endpoint for that missing functionality here:

• DELETE /follows/{userId}

Next, we should allow users to set their accounts to private or public. Public means any authenticated Beli user can view their restaurant reviews; private means only their followers can. We can use a property isPrivate in the request body. Not in the resource path, since according to REST semantics, that's only for identifiers of a resource. And not as a query parameter, since that's generally for modifying how a resource is retrieved (ex: filtering or sorting).

• PATCH /users/me {"isPrivate": true}
• PATCH /users/me {"isPrivate": false}

Next comes functionality for users to interact with restaurants. First is search. In the app, I see there's two input fields. The first has hint/placeholder text that says "Search restaurant, cuisine, occasion". The second field lets you put in a city. These can be included in the API route as query parameters. Finally, we can add pagination, and make it cursor-based so it's stable under changes and efficient for fetching each next page in stable log(n) time. Beli seems to have a limit of 10 results per 'page', and the cursor will be a base62-encoded string representing the restaurantId of the last restaurant on the current page, as well as the sort value for use in log(n) binary search.

• GET /restaurants?query={query}&city={city}&limit=10&cursor={base62-encoded-ptr}

To view restaurant details, users can call a GET request with the unique id of the restaurant.

• GET /restaurants/{restaurantId}

After viewing restaurant details, users may want to add a review for a restaurant. This will require an interesting API endpoint. We'll want a POST request to a route that includes the restaurant's unique ID. Not only that, we'll want to send over different types of data: notes, photos, score, etc. There are two complications:

1. Beli does scoring in an interesting way; you don't assign numeric ratings to a restaurant, but instead compare the restaurant to ones you've already rated. The comparisons are then processed by Beli's servers to output a numeric score. The API request only needs to send what a client sends to the server, thus the results of the comparisons: whichever restaurant was ranked immediately above or below. These are nullable fields, in case the restaurant being rated is placed at the top or bottom of the user's existing list (or both, if it's the first one!)
2. Instead of sending all the bytes of each photo's data through the same review request, I'll make the design decision to have a separate request (POST /photos) that is called for each submitted photo. The response returns a unique photoID that the actual review request can reference. This adds complexity, but it's worth the tradeoff for a couple reasons. First is that it makes sense for photo data to be stored separately from review data so separation of API endpoints is logical. This is because it's more scalable and cost-effective to store large, opaque byte files like photo data in object stores instead of relational databases (more on this later in the post). Second, if there's a failure in the upload of one of the photos, we don't need to resend a request to upload every photo at once; we've split up each of the photo uploads to their own request.

With those considerations, here are the relevant endpoints:

• POST /photos {"file": {photo_bytes}}
• POST /restaurants/{restaurantId}/reviews {"rankedAboveRestaurantId": {restaurantId}, "rankedBelowRestaurantId": {restaurantId}, "notes": {notes}, "photoIds": [{photoId}, ...]}

Next, users want a way to view created requests by other users. This is a simple GET request. The server can view the JWT in the request, find the user's information, and determine whether the user is allowed to view the reviews based on privacy settings.

• GET /users/{userId}/reviews

Users can receive notifications. These will be created by the servers whenever certain events happened, and can be queried simply. To take the design a step further, we can include an API endpoint that is called whenever a user views a notification, marking it as read. It uses a unique id for a notification. Since we aren't updating the resource (the notification) itself, but just updating a field like 'isRead', we use PATCH instead of POST for that.

• GET /notifications
• PATCH /notifications/{notificationId} {"isRead": true}

High level architecture

Now for the fun part, drawing! I'll use excalidraw.

First, something to call out. I'd like to have a distributed API gateway in front of my backend services guarding them like powerful frontline sentinels. Despite the added complexity, for a large scale system, it's good design to have a singular entry point (that is horizontally scaled) for a variety of reasons. I'll list them out:

• Load balancing. Our backend servers will be horizontally scaled and having logic to spread traffic as evenly as possible among them will make the best use of our system's server resources.
• Authorization. For authenticated requests from a client, the gateway can process the Json Web Token from it and ensure it's valid before forwarding requests to a backend service. This centralizes the logic, so not every single backend service needs to replicate auth handling logic.
• Rate limiting. The gateway can throttle requests from clients if they're sending too many, preventing issues like a malicious bot trying to overload our servers. This supports our nonfunctional requirement to remain available under unusually high traffic. I'll add a cache to store token buckets in-memory for quick access. Each token bucket is keyed by user ID for authenticated requests and by IP address for unauthenticated requests. I'll use Lua scripts on Redis for atomic operations when incrementing and reading from the cache data, since we'll have more than one gateway instance reading from the same cache at times. Or... instead of Redis, I could use an atomic, sharded, replicated, durable cache like the one I built in my own blog post series :)
• SSL/TLS termination; decrypt HTTPS traffic then use only HTTP when talking to internal services. HTTP is less secure, but when talking between our system's own services, it's a fine tradeoff. After all, we spend the CPU bandwidth to decrypt HTTPS traffic in the gateway so we don't have to do it in backend servers, while also getting to centralize certificate management to just the gateway servers. Efficient!
• Access logs for observability

Here’s the diagram so far! Our clients can’t do literally anything yet, but they can’t do it securely and at scale.

For the authentication routes, I want the client to be able to talk to some authentication service. Unauthenticated requests can hit the API gateway and then pass to the authentication service. The service can talk to an authentication database which has the following relational tables:

Users
- user_id (primary key)
- username
- password_hash
- private

RefreshSessions
- session_id (primary key)
- user_id (foreign key -> Users.user_id)
- refresh_token_hash
- expires_at
- revoked_at

I'd want follow functionality for creating and querying followers, with that data stored in a relational table like below. The composite primary key prevents the same user from following another user twice. We can add an index for followed_id for efficiently finding someone's followers. Adding an index means writes take longer, but it makes reads much faster. Users shouldn't have to wait long to see a followers list, and it's fine if it takes a bit of time for a new follow event to show up.

Follows
- follower_id (foreign key → Users.user_id)
- followed_id (foreign key → Users.user_id)
- status
- created_at
- PRIMARY KEY (follower_id, followed_id)

The User-centric logic described thus far can be owned by the Auth/User service, which makes use of the relational DB cluster.

A nice visual representation of one database cluster per table could work, and that has nice independant scaling and ownership separation, but that has issues like distributed transactions, operational complexity, network call latency, and more. So we can just have one database for all of that.

PostgreSQL is a good technology for our relational database since it supports transcations, indexing, joins, and more. It can have primary + read replicas for durability.

Users will want to find restaurants. The search function is more involved than just a simple query, though, since it's not like users search for restaurants by their id ("I can't wait to write about those bomb pancakes I had at 7Kp2mQ9xV4nR8tY3bW6cF1jH5sL0aDgZ!").

The search pipeline is quite involved, but it can broken down at a high level to the following flow: user query →  GET request → query processing → Elasticsearch candidate retrieval → geographic filtering → ranking → top-K restaurant lookup → response

I'll go into more depth on this in a deep dive below, but for this high level overview, I'll just share the high level breakdown of responsibilities between the two services I want to represent this functionality:

• Search service: query processing (spell correction, synonyms, tokenization, and filter parsing), top-K restaurant lookup from the DB
• Elasticsearch cluster: a technology for text search. Persists a derived inverted index and has functionality for candidate generation, filtering, and ranking.

Here's the database table for storing restaurant data:

Restaurants
- restaurant_id (primary key)
- name
- address
- city
- latitude
- longitude
- website_url
- phone_number
- average_score
- rating_count

Example walkthrough: a user in Redmond, WA searches 'Chipotles'. The resulting request is directed by the API gateway to the search service, which forwards it to the Elasticsearch cluster. The inverted index lookup finds a number of restaurantIDs associated with that keyword. Geographic filtering narrows it down to only restaurants within the area in and around Redmond. This ensures we don't overload the ranker with too many restaurantIDs. The ranker can quickly process the filtered list using signals like distance, score, personalization metrics, etc. then return an ordered list of restaurantIDs to the search service. The search service can then query PostgreSQL with those IDs to get all the restaurant metadata to send back to the user.

At this point, you might notice that we're pretty much just going through the entities list as we design each next table. It was handy coming up with that early on! That means you know what's next.

Reviews
- review_id (primary key)
- restaurant_id (foreign key → Restaurant.restaurant_id)
- user_id (foreign key → Users.user_id)
- notes
- photo_ids
- score
- created_at

I'm directly storing the 'notes' (the actual review text) in the Reviews table since I can add a constraint to the system by limiting how much text the user can put in, thereby limiting a user from uploading a full-text translation of The Odyssey into my poor little relational database.

Photos, on the other hand, are much too large to fit even after compression. As mentioned in API design, we can put them in an Object Store, and store only a link to them in our relational tables. It's much easier to query and maintain the photos and their metadata if each had a row in its own table instead of being an array in the Reviews table, hence what follows. I'm choosing to keep the object key separate from photo_id since the object key may contain file details (like a path in the object store) and that being separate from the photo_id lets us reorganize object storage without changing the database identity reference. A worthy trade-off for the little added storage. By the way, this is an example of normalization.

Photos
- photo_id (primary key)
- object_key
- review_id (foreign key -> Reviews.review_id)
- created_at

In the object store, we can use pre-signed URLs to let clients directly communicate with the photo data in storage, such as to upload photos. This is a reasonable tradeoff of security for performance. I'll use Azure's Blob Storage.

I will also use CDNs to cache photos for local restaurants near users geographically . This massively improves latency. Thus, a request to view a photo first checks the CDN. On a cache miss, it fetches the photo from object storage, caches it, and returns it to the client.

We have a busy diagram but we're not done yet. Just one last piece of functionality: notifications!

Notifications
- notification_id (primary key)
- user_id (foreign key → Users.user_id)
- created_at
- isRead

However, the twist is that our diagram doesn't have to change. Notifications are just logs of what our other services are doing (user X followed user Y, user Z just reviewed Restaurant A, etc.). These can update the Notifications table concurrently to their main data update in a transaction. There can also be notifications like 'you haven't reviewed a restaurant in over a week!' (very on-point for Beli), and that can run as some scheduled job in our Auth / User service. When a user queries their notifications, that can run through that service as well, since it's a user-centric operation and thus can scale accordingly with the number of users our service supports.

Deep dive: Geospatial Indexes

Restaurant search must efficiently filter and rank results by proximity. A naive scan that calculates the distance from the user to every restaurant would become too expensive at scale, so I’ll examine how geospatial indexes narrow the search space to nearby candidates. Geospatial algorithms are of particular interest to me, given my past research.

How do we use an index for two-dimensional space? Each location is represented as a longitude and latitude value, after all. There are different approaches, but one I really like (especially as a board game fan) is to partition geographic space into hexes. These tesellate (meaning they can cover a space without gaps or overlaps) and unlike squares, which also tesellate, they're more circular which represents edge distance better, and avoids issues like the square pattern's diagonal neighbors being further away. Then, we can associate each hex with a list of restaurantIDs. When a user performs a restaurant search, we can filter to only restaurants in their hex as well as neighboring hexes within a certain distance of hexes. Hex distance can be used as one factor in the subsequent ranking process.

There's a decision to make with how big each hex should be. Smaller hexes mean more granularity/precision of candidate generation, but require a larger index and query overhead.

There are additional edge case considerations. If a hex is two away from a user, but the hex in between is just water, should the hex actually be considered to have a larger distance than '2'? Same with national borders. A user is more likely to drive 50 miles north for a restaurant in the same country versus driving just 10 miles south to an entirely different country.

Deep dive: Kafka and the Pub-Sub pattern

One issue with our current system is the tight coupling. Imagine a user creates a review for a restaurant. This uploads the attached photos and adds in the review to the database, yes, but several other downstream events occur. We need to update the Notifications table. We need to update our personalization engine in the search ranker. We may want extensibility in our system for more features, such as building recommendations for each user, or creating an activity feed on user profiles. The problem with all these being tightly coupled is that if one function fails, then we need to rollback and retry everything.

The solution is to decouple the events; to make them asynchronous. For this, we can metamorphosize our system by introducing Kafka.

It utilizes the publisher-subscriber (or 'pub-sub') pattern. The event generator is the publisher, creating a message (ex: a newly created review) that is stored in an append-only queue. The event listeners are the subscriber, who read from the queue to perform their functionality (ex: the notification service creating a 'review created' row in the Notifications table).

The subscribers each can independently track their offset in the queue, so they can read and process the messages at their own pace. We don't delete from the queue when a subscriber reads from it, since we have multiple of them. This is the main reason I chose Kafka over RabbitMQ, a different message queue technology; RabbitMQ is designed to delete messages as they are processed.

Our system has high scale. One queue definitely won't work, so we can do the ol' reliable: horizontal partitioning. Our partition key should be chosen appropriately, since each queue can only guaruntee ordering within itself. UserID hash is the perfect choice for Beli, since our messages are user-centric, focusing on activity per user.

We also want durability. We can have replicas for each queue to handle failover.

What happens if a message fails to process? Perhaps an intern was trusted a little too much and accidentally pushed a change that broke a subscriber. We can implement monitoring and alerting, but suppose that doesn't trigger a rollback in time. If the subscriber keeps retrying to process the message, and keeps failing, it will block the system! A solution is to configure a max retry count. If that is exceeded, just throw the message away in the garbage can. Don't forget that as software engineers, it's important to rummage through the garbage for information! We want to inspect it to see what went wrong (or rather, we can tell our AI agent to do that dirty work), so the garbage can should be accessible with a short TTL. In the message queue world, we call the garbage can a 'dead letter queue'.

Deep dive: Handling various tricky edge cases

The real world is messy and comes with many ways to break even a robust-looking system. In this deep dive, I'll cover various little edge cases that I haven't explicitly mentioned how to handle yet.

Edge case: what happens if there are duplicate submissions?

POST requests are not idempotent by nature. But suppose a user is experiencing lag and clicks the Submit button once... and it doesn't go through. So they click again... and again... and perhaps again. Once the requests go through, he scoring mechanism gets corrupted, the user gets multiple notifications, and our personalization models process what was effectively the same review repeatedly.

One solution is to make our Reviews table unique on every user + restaurant combination. However, this would prevent our users from updating/re-reviewing a restaurant.

A better, yet more complex solution, is to add a client-generated Idempotency-Key header. We can have a short-TTL Redis cache that stores idempotency keys we've already processed recently (ex: past 24 hours). That way we can easily reject duplicate requests.

We don't use review_id as the idempotency key since those are server-generated whenever it receives a request, meaning duplicates will just get different ids.

Edge case: What happens if restaurant gets so viral it has millions of reviews?

This is a common issue of 'hot partitions'. If a partition keyed by restaurant_id, such a DB partition, handles high scale, 'hot' traffic, the shard's CPU saturates, timing out requests. My preferred solution is splitting up hot shards by adding a salt in front of the partition key.

This is what I fondly call 'Salting Taylor Swift' because of how often educational resources invoke her name when explaining the reason for hot shards. Taylor Swift is not a restaurant, unfortunately, so I cannot use her as an example of this concept as it relates to Beli.

Edge case: What happens when a popular CDN-cached photo expires

A cache stampede occurs when a frequently accessed cached item in the CDN expires, causing numerous simultaneous requests to miss the ache and overwhelm the object store to regenerate the same data.

One solution is to use a distributed lock so only one of those requests goes through, thus re-populating the CDN for the rest of the requests to use. Another solution, which likely requires more engineering effort, is prewarming: update the CDN's popular photos by syncing with the object store shortly before they expire.