Design Online Auction

1. The system should maintain strong consistency for bids to ensure all users see the same highest bid.
2. The system should be fault tolerant and durable. We can't drop any bids.
3. The system should display the current highest bid in real-time so users know what they are bidding against.
4. The system should scale to support 10M concurrent auctions.

• The system should have proper observability and monitoring.
• The system should be secure and protect user data.
• The system should be well tested and easy to deploy (CI/CD pipelines)

Requirements

The Set Up

Defining the Core Entities

1. Auction : This represents an auction for an item. It would include information like the starting price, end date, and the item being auctioned.
2. Item : This represents an item being auctioned. It would include information like the name, description, and image.
3. Bid : This represents a bid on an auction. It would include information like the amount bid, the user placing the bid, and the auction being bid on.
4. User : This represents a user of the system who either starts an auction or bids on an auction.

Core Entities

API or System Interface

POST /auctions -> Auction & Item
{
    item: Item,
    startDate: Date,
    endDate: Date,
    startingPrice: number,    
}

POST /auctions/:auctionId/bids -> Bid
{
    Bid
}

GET /auctions/:auctionId -> Auction & Item

High-Level Design

1) Users should be able to post an item for auction with a starting price and end date.

Create an Auction

1. Client Users will interact with the system through the clients website or app. All client requests will be routed to the system's backend through an API Gateway.
2. API Gateway The API Gateway handles requests from the client, including authentication, rate limiting, and, most importantly, routing to the appropriate service.
3. Auction Service The Auction Service, at this point, is just a thin wrapper around the database. It takes the auction details from the request, validates them, and stores them in the database.
4. Database The Database stores tables for auctions and items.

1. Client sends a POST request to /auctions with the auction details.
2. API Gateway routes the request to the Auction Service.
3. Auction Service validates the request and stores the auction and item data in the database.
4. Database stores the auction and item data in tables.

2) Users should be able to bid on an item. Where bids are accepted if they are higher than the current highest bid.

1. Validate incoming bids (e.g. check bid amount is higher than current max)
2. Update the auction with new highest bid
3. Store bid history in the database
4. Notify relevant parties of bid updates

1. Independent Scaling : Bidding traffic is typically much higher volume than auction creation - we expect ~100x more bids than auctions. Having a separate service allows us to scale the bidding infrastructure independently.
2. Isolation of Concerns : Bidding has its own complex business logic around validation, race conditions, and real-time updates. Keeping it separate helps maintain clean service boundaries.
3. Performance Optimization : We can optimize the bidding service specifically for high-throughput write operations, while the auction service can be optimized for read-heavy workloads.

Place Bids

1. Client sends a POST request to /auctions/:auctionId/bids with the bid details.
2. API Gateway routes the request to the Bidding Service.
3. Bidding Service queries the database for the highest current bid on this auction. It stores the bid in the database with a status of either "accepted" (if the bid is higher than current highest) or "rejected" (if not). The service then returns the bid status to the client.
4. Database bids are stored in a new bids table, linked to the auction by auctionId.

3) Users should be able to view an auction, including the current highest bid.

1. They want to learn about the item in case they decide they're interested in buying it.
2. They want to place a bid, so they need to know the current highest bid that they need to beat.

View Auction

Potential Deep Dives

1) How can we ensure strong consistency for bids?

• The current highest bid is $10 .
• User A decides to place a bid of $100 .
• User B decides to place a bid of $20 shortly after.

1. User A's Read : User A reads the current highest bid, which is $10.
2. User A's Write : User A writes their bid of $100 to the database. The system accepts this bid because $100 is higher than $10.
3. User B's Read : User B reads the current highest bid. Due to a delay in data propagation or read consistency issues, they still see the highest bid as $10 instead of $100.
4. User B's Write : User B writes their bid of $20 to the database. The system accepts this bid because $20 is higher than $10 (the stale value they read earlier).

• A bid of $100 from User A (the actual highest bid).
• A bid of $20 from User B (which should have been rejected).

Bad Solution: Row Locking with Bids Query

Approach

One initial approach might be to use row-level locking with a query to get the current maximum bid. When a user tries to place a bid, we need to ensure that no other bids are being processed for the same auction simultaneously to avoid race conditions. Here's how we could implement this:

1. Begin a transaction : Start a database transaction to maintain atomicity.
2. Lock all bid rows for the auction using SELECT ... FOR UPDATE : This locks all existing bids for the auction, preventing other transactions from modifying them until the current transaction is complete.
3. Query the current maximum bid from the bids table : Retrieve the highest bid currently placed on the auction.
4. Compare the new bid against it : Check if the incoming bid amount is higher than the current maximum bid.
5. Write the new bid if accepted : Insert the new bid into the bids table.
6. Commit the transaction : Finalize the transaction to persist changes.

Here's what the SQL query could look like:

BEGIN;

WITH current_max AS (
    SELECT MAX(amount) AS max_bid
    FROM bids
    WHERE auction_id = :auction_id
    FOR UPDATE
)
INSERT INTO bids (auction_id, user_id, amount, bid_time)
SELECT :auction_id, :user_id, :amount, NOW()
FROM current_max
WHERE :amount > COALESCE(max_bid, 0)
RETURNING id;

COMMIT;

Challenges

While this approach ensures that no two bids are processed concurrently for the same auction, it has significant drawbacks:

1. Performance and Scalability Issues : Locking all bid rows for an auction serializes bid processing, creating a major bottleneck. As the number of concurrent auctions and bids increases, the contention for locks intensifies, leading to increased latency and poor user experience. The database may even escalate to table-level locks under heavy load, blocking all operations on the bids table.
2. Poor User Experience : The delays introduced by lock contention and serialized processing result in slow response times or timeouts when placing bids. This is unacceptable in a competitive bidding environment where users expect real-time responsiveness and consistent performance.

In general, this is a big no-no. You want to use row locking sparingly and with optimizations to ensure that a) you lock as few rows as possible and b) you lock rows for as short of a duration as possible. We don't respect either of these principles here.

Good Solution: Cache max bid externally

Approach

The next thing most candidates think of is to cache the max bid in memory. They realize that the main issue with the above approach is that we are holding the lock on a large number of rows for a reasonable duration, since we need to query the bid table to calculate the max bid each time.

To avoid this, we can cache the max bid in memory in something like Redis. Now, the data flow when a bid comes in looks very different:

1. Read cache : Read the max bid for the given auction from Redis.
2. Update cache : If the new bid is higher, update the cache with the new max bid.
3. Write bid : Write the bid to the database with a status of accepted or rejected.

Cache max bid

Challenges

We solved one problem, but created another. Now we've moved this from a consistency problem within the database to a consistency problem between the database and the cache. We need a couple things to be true:

1. We need the cache read and cache write to happen atomically so we don't have a race condition like in our initial scenario. Fortunately, this is easy enough as Redis is single threaded and supports atomic operations. We can use either Redis transactions or Lua scripting to ensure our read-modify-write sequence happens as one operation:

   -- Lua script to atomically compare and set max bid
   local current_max_bid = tonumber(redis.call('GET', auction_key) or '0')
   local proposed_bid_amount = tonumber(proposed_bid)
   
   if proposed_bid_amount > current_max_bid then
       redis.call('SET', auction_key, proposed_bid_amount)
       return true
   else
       return false
   end

2. We need to make sure that our cache is strongly consistent with the database. Otherwise we could find ourselves in a place where the cache says the max bid is one thing but that bid is not in our database (because of failure or any other issue). To solve this, we have a few options:

   • Use distributed transactions (two-phase commit) to ensure atomicity across Redis and the database. This adds significant complexity and performance overhead.
   • Accept Redis as the source of truth during the auction and write to the database asynchronously. This trades consistency for performance.
   • Use optimistic concurrency with retry logic: update the cache atomically first, then write to the database. If the database write fails, roll back the cache update.

Most importantly, if you find yourself in an interview where a distributed transaction is needed, consider whether you can restructure your system to avoid it.

Great Solution: Cache max bid in database

Approach

We solved the issue with locking a lot of rows for a long time by moving the max bid to a cache, but that introduced a new issue with consistency between the cache and the database. We can solve both problems by storing the max bid in the database. Effectively using the Auction table as our cache.

Now, our flow looks like this:

1. Lock the auction row for the given auction (just one row)
2. Read the max bid for the given auction from the Auction table.
3. Write the bid to the database with a status of accepted or rejected.
4. Update the max bid in the Auction table if the new bid is higher.
5. Commit the transaction.

We now only lock a single row and for a short duration. If we want to avoid pessimistic locking altogether, we can use optimistic concurrency control (OCC) .

OCC is ideal for our system because bid conflicts are relatively rare (most bids won't happen simultaneously on the same auction). Here's how it works:

1. Read the auction row and get the current max bid (this is what is referred to as the 'version' with OCC)
2. Validate that the new bid is higher than the max bid
3. Try to update the auction row, but only if the max bid hasn't changed:

   UPDATE auctions 
   SET max_bid = :new_bid 
   WHERE id = :auction_id AND max_bid = :original_max_bid

4. If the update succeeds, write the bid record. If it fails, retry from step 1.

This approach avoids locks entirely while still maintaining consistency, at the cost of occasional retries when conflicts do occur.

Cache max bid in DB

2) How can we ensure that the system is fault tolerant and durable?

1. Durable Storage : When a bid comes in, we immediately write it to the message queue. Even if the entire Bid Service crashes, the bid is safely stored and won't be lost. Think of it like writing your name on a waiting list at a restaurant - even if the host takes a break, your place in line is secured.
2. Buffering Against Load Spikes : Imagine a popular auction entering its final minutes. We might suddenly get thousands of bids per second - far more than our Bid Service can handle. Without a message queue, we'd have to either:

   • Drop bids (unacceptable)
   • Crash under the load (also unacceptable)
   • Massively over-provision our servers (expensive)

   With a message queue, these surge periods become manageable. The queue acts like a buffer, storing bids temporarily until the Bid Service can process them. It's like having an infinitely large waiting room for your bids.
3. Guaranteed Ordering : Message queues (particularly Kafka) can guarantee that messages are processed in the order they were received. This is important for fairness - if two users bid the same amount, we want to ensure the first bid wins. The queue gives us this ordering for free.

Fault tolerant system

1. High Throughput : Kafka can handle millions of messages per second, perfect for high-volume bidding periods.
2. Durability : Kafka persists all messages to disk and can be configured for replication, ensuring we never lose a bid.
3. Partitioning : We can partition our queue by auctionId, ensuring that all bids for the same auction are processed in order while allowing parallel processing of bids for different auctions.

1. User submits a bid through our API
2. API Gateway routes to a producer which immediately writes the bid to Kafka
3. Kafka acknowledges the write, and we can tell the user their bid was received
4. The Bid Service consumes the message from Kafka at its own pace
5. If the bid is valid, it's written to the database
6. If the Bid Service fails at any point, the bid remains in Kafka and can be retried

3) How can we ensure that the system displays the current highest bid in real-time?

1. Too slow : We're updating the highest bid every few seconds, but for a hot auction, this may not be fast enough.
2. Inefficient : Every client is hitting the database on every request, and in the overwhelming majority of cases, the max bid hasn't changed. This is wasteful.

Good Solution: Long polling for max bid

Approach

Long polling offers a significant improvement over regular polling by maintaining an open connection to the server until new data is available or a timeout occurs. When a client wants to monitor an auction's current bid, they establish a connection that remains open until either the maximum bid changes or a timeout is reached (typically 30-60 seconds).

The server holds the request open instead of responding immediately. When a new bid is accepted, the server responds to all waiting requests with the updated maximum bid. The clients then immediately initiate a new long-polling request, maintaining a near-continuous connection.

The client side implementation typically looks something like this:

async function pollMaxBid(auctionId) {
  try {
    const response = await fetch(`/api/auctions/${auctionId}/max-bid`, {
      timeout: 30000 // 30 second timeout
    });
    
    if (response.ok) {
      const { maxBid } = await response.json();
      updateUI(maxBid);
    }
  } catch (error) {
    // Handle timeout or error
  }
  
  // Immediately start the next long poll
  pollMaxBid(auctionId);
}

On the server side, we maintain a map of pending requests for each auction. When a new bid is accepted, we respond to all waiting requests for that auction with the new maximum bid.

Challenges

While long polling is better than regular polling, it still has some limitations. The server must maintain open connections for all clients watching an auction, which can consume significant resources when dealing with popular auctions. Additionally, if many clients are watching the same auction, we might face a "thundering herd" problem where all clients attempt to reconnect simultaneously after receiving an update.

The timeout mechanism also introduces a small delay - if a bid comes in just after a client's previous long poll times out, they won't see the update until their next request completes. This creates a tradeoff between resource usage (shorter timeouts mean more requests) and latency (longer timeouts mean potentially delayed updates).

Lastly, scaling becomes a challenge since each server needs to maintain its own set of open connections. If we want to scale horizontally by adding more servers, we need additional infrastructure like Redis or a message queue to coordinate bid updates across all servers. This adds complexity and potential points of failure to the system. More on this when we discuss scaling.

Great Solution: Server-Sent Events (SSE)

Approach

Server-Sent Events (SSE) provides a more elegant solution for real-time bid updates. SSE establishes a unidirectional channel from server to client, allowing the server to push updates whenever they occur without requiring the client to poll or maintain multiple connections.

When a user views an auction, their browser establishes a single SSE connection. The server can then push new maximum bid values through this connection whenever they change. This creates a true real-time experience while being more efficient than both regular polling and long polling.

The client-side implementation is remarkably simple:

const eventSource = new EventSource(`/api/auctions/${auctionId}/bid-stream`);

eventSource.onmessage = (event) => {
  const { maxBid } = JSON.parse(event.data);
  updateUI(maxBid);
};

On the server side, we maintain a set of active SSE connections for each auction. When a new bid is accepted, we push the updated maximum bid to all connected clients for that auction. The server implementation might look something like this:

class AuctionEventManager {
  private connections: Map<string, Set<Response>> = new Map();
  
  addConnection(auctionId: string, connection: Response) {
    if (!this.connections.has(auctionId)) {
      this.connections.set(auctionId, new Set());
    }
    this.connections.get(auctionId).add(connection);
  }
  
  broadcastNewBid(auctionId: string, maxBid: number) {
    const connections = this.connections.get(auctionId);
    if (connections) {
      const event = `data: ${JSON.stringify({ maxBid })}\n\n`;
      connections.forEach(response => response.write(event));
    }
  }
}

You could use websockets here as well, but SSE is arguably a better fit given the communication is unidirectional and SSE is typically lighter weight and easier to implement.

SSE

Challenges

The main challenge is scaling the real-time updates across multiple servers. As our user base grows, we'll need multiple servers to handle all the SSE connections. However, this creates a coordination problem: when a new bid comes in to Server A, there may be users watching that same auction who are connected to Server B. Without additional infrastructure, Server A has no way to notify those users about the new bid, since it only knows about its own connections.

For example, imagine User 1 and User 2 are both watching Auction X, but User 1 is connected to Server A while User 2 is connected to Server B. If User 3 places a bid that goes to Server A, only User 1 would receive the update - User 2 would be left with stale data since Server B doesn't know about the new bid.

We'll talk about the solution this this problem next as we get into scaling.

4) How can we ensure that the system scales to support 10M concurrent auctions?

1. What are the resource requirements at peak? Consider storage, compute, and bandwidth.
2. Does the current design satisfy the requirement at peak?
3. If not, how can we scale the component to meet the new requirement?

Scale

Some additional deep dives you might consider

1. Dynamic auction end times : How would you end an auction dynamically such that it should be ended when an hour has passed since the last bid was placed? For this, there is a simple, imprecise solution that is likely good enough, where you simply update the auction end time on the auction table with each new bid. A cron job can then run periodically to look for auctions that have ended. If the interviewer wants something more precise, you can add each new bid to a queue like SQS with a visibility timeout of an hour. A worker will process each item after an hour and check if that bid is still winning. If yes, end the auction.
2. Purchasing : Send an email to the winner at the end of the auction asking them to pay for the item. If they fail to pay within N minutes/hours/days, go to the next highest bidder.
3. Bid history : How would you enable a user to see the history of bids for a given auction in real-time? This is basically the same problem as real-time updates for bids, so you can refer back to the solution for that.

What is Expected at Each Level?

Mid-level

Senior

Staff