System requirements

Functional:

• User can bid an item.
• User can see the current highest bid for any item.
• If there is no new bid for 1 hour, user with highest bid will get notification to submit payment within 10 min. If payment success, the user win the bid.

Non-Functional:

• Low latency: The bid price should be low latency to view and submit bid.
• High availability and Reliability: The auction system should be highly available to users.
• Security: The bid and payment from users information must be secure.

Capacity estimation

Assume daily active user is 10m.

Read QPS: 10m / 100k = 100

Peak read QPS: 100 * 2 = 200

Assume 10% user bid 1 item per day

Write QPS: 10m * 10% / 100k = 10

DB usage capacity:

Each bid may take up to 1kb to save.

Daily DB usage: 10m * 10% * 1kb = 1GB

Yearly DB usage: 1GB * 400 = 400GB

We need 3 replica. So yearly DB usage: 400GB * 3 = 1.2 TB

API design

REST api:

1. POST bidItem
2. PUT updateDid
3. GET getItemBid

WebSocket message:

1. From Client to server: subscribeToItem
2. From Client to server: unsubscribeToItem
3. From server to client: getItemBid

Database design

I choose SQL db.

The main schema of Item table:

id (primary key)

name

highestBidId (reference key to bid table)

The main schema of bid table:

id (primary key)

itemId (reference key to item table)

status (enum: bidWon, bidLoss, bidComplete, bidFail)

price

createdAt

updatedAt

High-level design

1. Client: Web and mobiles applications to view and submit the bid.
2. Load balance: Load balance the traffic by path based and round-robin approach.
3. API Gateway: Authentication, rate limiting, security and keep an WebSocket connection with client.
4. Bid read service: check and response the item highest bid from DB cache.
5. WebSocket session NoSQL DB: Store which API Gateway keep the webSocket connection with which client.
6. bid write service: Write the latest bid to SQL DB.
7. SQL DB: Source of truth for the item and bid information.
8. DB Cache: Cache layer of the SQL DB for fast reading.
9. Job Scheduler: Create jobs when bids expire. Trigger a notification to user if the bid won through notification service.
10. Notification service: Send notification to users through SMS, email and push notifications if users win bids.

Request flows

The design separate read and write requests workflow

1. Client send a GET request to get current bid for certain items. The request go through load balance to be routed to the correct api gateway. The api gateway send the request to bid read service. The bid read service will read DB cache to get the response the bid back to client.
2. Client set up a WebSocket connection with server. When browsing items, the client send a subscription request to the server. Any bid updates for the item will be send back to the client through the WebSocket connection. When client stops browsing the item, client will send an unsubscribe message to server to stop subscribing the item.
3. Client submit a bid request. The request will be routed to bid write service through load balance and api gateway. The bid write service will update the db for the new bid. The bid write service will also create a scheduled job through the job scheduler. The job scheduler will schedule a job. When the bid expires, the job will update the DB and Notification service that the bid wins. If a new higher bid comes before the current bid expires, the current job will be cancel and a new job will be scheduled.
4. If the bid win, the notification service will send notification to users through SMS, email, push notifications to ask user to submit payment.

Detailed component design

Deep dive into the SQL Database

The most important part for the Database is to make sure there is no double bidding for same item.

To make sure double bidding won't happen, there are two locking mechanisms to make sure two requests won't update the same database row at the same time.

1. Pessimistic locking. For the pessimistic locking, when one entry is trying to be updated, the database entry will be locked first. After the entry updated or the updated failed, the lock will be released. Then the same entry could be updated by other request. Pessimistic locking is simpler to implement. But it has a higher latency because each of the entry update needs to lock the entry first.
2. Optimistic locking. For optimistic locking, the database entry won't be locked for update. If two requests try to update the same entry at the same time, the first request will update the entry and update the version number of the entry, then the second request notice the version of the entry has already update, then it will return error message and won't update entry. The optimistic locking is faster and low latency. But if the request failed, the bid writing service will be responsible to reverse the DB to previous state. The implementation details are more complex.

Since the auction system requires low latency, I will choose to use optimistic locking.

Deep dive into the bid write service

When horizontal scaling, the bid write service could be sharded by itemIds so to make the same item go to the same server. The server could have a local cache of the top bid for certain items. This is to reduce the request to DB if the new bid is lower than the local cache in the bid write service. Even if we introduce a state in the service, when the service failed, it is easy to recreate the state by querying the SQL DB cache. The cache DB data may not update to date, but it is good enough to do the first level check.

Trade offs/Tech choices

First trade offs when writing a new bid to DB.

There are three options:

1. Write through. The new bid will be written to both SQL DB and Cache DB together. Only both write operations success, the bid write service returns a success message. This option will guaranty strong consistency between SQL DB and Cache DB. But this option will have high latency because the write operation need to update both SQL DB and Cache DB. If one operation fails, the other operation need to be reversed.
2. Write Back. The new bid will only be written to the cache DB. The cache DB will be responsible to update the SQL DB. In this operation, the cache DB became the source of truth. This option has the lowest latency. The trade off is that this option will eventual consistency. In addition, there will be extra effort to deal with cache DB failing case. For example, we could use even sourcing patterns and create snapshot for events, if the cache DB failed, it could be recovered from the snapshot. Also the cache DB must handle the case to handle concurrent DB writing with lock mechanism or version control. The implementation is more complicate.
3. The third option is similar to the second option. The write operation will only update the SQL DB. Then the SQL DB will update the cache DB. The SQL DB is the source of truth. The cache DB will only be responsible to read operation. This option has low latency. The trade off is eventual consistency on read side. This option is simpler to implement because the SQL DB handles the concurrent operation and lock mechanism.

For this design, I will choose option 3 considering the low latency and high availability requirement.

Failure scenarios/bottlenecks

Try to discuss as many failure scenarios/bottlenecks as possible.

Future improvements

What are some future improvements you would make? How would you mitigate the failure scenario(s) you described above?