Design an online auction

01The design, in the six-step framework

1. Requirements and use cases

An auction takes bids for one item until a deadline and names exactly one winner. The hard part is the last second: many bids arrive together and the closing must be atomic.

• A seller lists an item with a starting price, a minimum increment and a closing time.
• A bidder places a bid; it is accepted only if the auction is open and the bid beats the current price by the increment.
• Bidders are notified when outbid and when the auction closes.
• The system closes the auction at the deadline and declares the highest bid the winner; a bid arriving after the close is rejected.
• Anyone reads the current price and bid history.

Out of scope: payment, proxy bidding beyond a mention, and multiple items per lot. Non-functional constraints: exactly one winner even under concurrent bids at the deadline; the state machine is explicit; notification is decoupled from bidding.

2. Core entities and relationships

• Item: what is sold; a value.
• Bid: an immutable record (bidder, amount, time, sequence).
• Auction: the item, the rules, the ordered bids, the state and a lock.
• AuctionState: DRAFT, OPEN, CLOSED, CANCELLED, with a transition table.
• AuctionListener: notified on new high bid and on close.
• Clock: injected so the deadline is testable.
• AuctionHouse: creates and looks up auctions and runs the closer.

The auction composes its bids: a bid is meaningless without its auction and is never shared. The house composes auctions and injects the clock so tests can move time.

3. Interfaces and key methods

class Clock(Protocol):
    def now(self) -> float: ...

class AuctionListener(Protocol):
    def outbid(self, auction: Auction, previous: Bid, new: Bid) -> None: ...
    def closed(self, auction: Auction, winner: Optional[Bid]) -> None: ...

class Auction:
    def place(self, bidder: str, amount: int, now: float) -> Bid:
        """Under the lock: open, not past deadline, amount >= current + increment; else raise BidRejected."""
    def close(self, now: float) -> Optional[Bid]:
        """Under the lock: OPEN -> CLOSED once; returns the winning bid or None."""
    def current_price(self) -> int: ...
    def leader(self) -> Optional[Bid]: ...

class AuctionHouse:
    def create(self, item: Item, increment: int, closes_at: float) -> Auction: ...
    def bid(self, auction_id: str, bidder: str, amount: int) -> Bid: ...
    def close_due(self) -> list[Auction]:
        """Close every open auction whose deadline has passed."""

Invariants: bids in auction.bids are strictly increasing in amount and in sequence; leader() is the last bid; after CLOSED no bid is ever appended; closed is delivered to listeners exactly once per auction.

4. Design patterns and the choices behind them

A lock around place and close

The deadline race is two bids and the closer arriving in the same millisecond. One lock per auction, held for the whole of place and close, makes them serial: whichever runs first wins, and the later one sees either a higher price or a closed state. The check of now > closes_at inside place means a late bid is rejected even if the closer has not yet run.

State machine with a table

DRAFT to OPEN to CLOSED, with CANCELLED reachable from DRAFT and OPEN. The state table gives idempotent closing for free: a second close is an illegal transition and does nothing, which protects the exactly-once notification.

Observers for outbid and closed

Email, push and a UI feed all care about the same two events. Listeners are called after the lock is released, so a slow notifier cannot hold up bidding.

Bids as immutable values

A frozen Bid with a sequence number is the audit trail; ties on amount are impossible because each bid must exceed the previous by the increment, and ties in time are broken by sequence.

5. Core flow and code

1. house.bid reads the clock and calls auction.place.
2. place takes the lock, checks state and deadline, checks the increment, appends the bid, records the previous leader, releases the lock and notifies outbid.
3. A scheduler calls close_due periodically; each due auction's close flips the state under the lock and notifies closed once.

from __future__ import annotations
import itertools, threading, time
from dataclasses import dataclass, field
from enum import Enum
from typing import Optional, Protocol


class BidRejected(Exception): ...
class IllegalTransition(Exception): ...


class AuctionState(Enum):
    DRAFT = "draft"; OPEN = "open"; CLOSED = "closed"; CANCELLED = "cancelled"


ALLOWED = {AuctionState.DRAFT: {AuctionState.OPEN, AuctionState.CANCELLED},
           AuctionState.OPEN: {AuctionState.CLOSED, AuctionState.CANCELLED},
           AuctionState.CLOSED: set(), AuctionState.CANCELLED: set()}


@dataclass(frozen=True)
class Item:
    id: str
    title: str
    start_price: int


@dataclass(frozen=True)
class Bid:
    bidder: str
    amount: int
    at: float
    seq: int


class Clock(Protocol):
    def now(self) -> float: ...


class SystemClock:
    def now(self) -> float: return time.time()


class AuctionListener(Protocol):
    def outbid(self, auction: Auction, previous: Bid, new: Bid) -> None: ...
    def closed(self, auction: Auction, winner: Optional[Bid]) -> None: ...


class Auction:
    def __init__(self, auction_id: str, item: Item, increment: int, closes_at: float) -> None:
        self.id, self.item, self.increment, self.closes_at = auction_id, item, increment, closes_at
        self.state = AuctionState.DRAFT
        self.bids: list[Bid] = []
        self.listeners: list[AuctionListener] = []
        self.lock = threading.Lock()
        self._seq = itertools.count(1)

    def _move(self, to: AuctionState) -> None:
        if to not in ALLOWED[self.state]:
            raise IllegalTransition(f"{self.state.value} -> {to.value}")
        self.state = to

    def open(self) -> None:
        with self.lock:
            self._move(AuctionState.OPEN)

    def current_price(self) -> int:
        return self.bids[-1].amount if self.bids else self.item.start_price

    def leader(self) -> Optional[Bid]:
        return self.bids[-1] if self.bids else None

    def place(self, bidder: str, amount: int, now: float) -> Bid:
        with self.lock:
            if self.state is not AuctionState.OPEN or now >= self.closes_at:
                raise BidRejected("auction is not open")
            floor = self.current_price() + (self.increment if self.bids else 0)
            if amount < floor:
                raise BidRejected(f"bid must be at least {floor}")
            previous = self.leader()
            bid = Bid(bidder, amount, now, next(self._seq))
            self.bids.append(bid)
        if previous is not None:
            for l in self.listeners:
                l.outbid(self, previous, bid)
        return bid

    def close(self, now: float) -> Optional[Bid]:
        with self.lock:
            if self.state is not AuctionState.OPEN or now < self.closes_at:
                return self.leader() if self.state is AuctionState.CLOSED else None
            self._move(AuctionState.CLOSED)
            winner = self.leader()
        for l in self.listeners:
            l.closed(self, winner)
        return winner


class AuctionHouse:
    def __init__(self, clock: Clock) -> None:
        self.clock = clock
        self.auctions: dict[str, Auction] = {}
        self._ids = itertools.count(1)

    def create(self, item: Item, increment: int, closes_at: float) -> Auction:
        a = Auction(f"a{next(self._ids)}", item, increment, closes_at)
        self.auctions[a.id] = a
        a.open()
        return a

    def bid(self, auction_id: str, bidder: str, amount: int) -> Bid:
        return self.auctions[auction_id].place(bidder, amount, self.clock.now())

    def close_due(self) -> list[Auction]:
        now = self.clock.now()
        done = []
        for a in self.auctions.values():
            if a.state is AuctionState.OPEN and now >= a.closes_at:
                a.close(now); done.append(a)
        return done

6. Extensions, concurrency and what interviewers probe

• Anti-sniping: extend closes_at by a minute when a bid lands in the last minute. It is one line inside place, under the lock, and the closer must re-read the deadline, which it does.
• Proxy bidding (bid up to a maximum automatically) is a listener on outbid that places a new bid on the bidder's behalf; it reuses place and its rules, and must not run while holding the auction lock, which is why notifications happen after release.
• Why notify outside the lock: a listener that bids back would deadlock on a non-reentrant lock, and a slow email call would stall every bidder.
• Clock injection: the deadline test is only deterministic with a fake clock; name this before being asked and the concurrency questions get easier.
• Test first: ten threads bidding increasing amounts on one auction leave a strictly increasing bid list; a bid at exactly closes_at is rejected; close called twice notifies once; a bid below current plus increment is rejected with the floor in the message.
• Reserve price: a hidden minimum is one more field on Auction, checked in close; if the leader is below it, the winner is None and the item stays unsold. Bidders see the current price, never the reserve.
• Cancelling an open auction is allowed by the table, but must take the same lock as place, or a bid can land on a cancelled auction and a bidder is told they lead an auction that no longer exists.
• Common mistake: checking the deadline in the house and not in place. The window between the check and the append is exactly where a late bid slips in.

02Where this question was reported

• GitHub · awesome-low-level-design, Medium
• Codemia · Codemia Medium
• LeetCode Discuss · LeetCode Design Auction System, Google-tagged (freq 5.6)
• LLD Canvas · Auction as state machine (open/bidding/closed)