Notes
Requirements
Fix the scope. A seller lists an item with a start time, an end time, a starting price, a minimum increment and an optional hidden reserve price. While the auction is live, bidders place bids and everyone can see the highest one. A bidder who is outbid gets a notification. At the end time the auction closes and picks a winner. Many bidders act at once. Payment and search are out of scope.
Ask the questions that turn into rules. Does the winner pay their own bid? Yes. How much must a new bid beat the top one by? At least the minimum increment. If the reserve is not met, there is no sale and the seller is told. The seller cannot bid on their own item. A bid counts only if it arrives strictly before the end time. Automatic proxy bidding comes later as an extension.
- seller lists an item with
- start time and end time
- starting price, min increment,
- hidden reserve price
- bidders place bids while live
- show the highest bid
- notify a bidder when outbid
- close at end time, pick winner
- many bidders at once
- out of scope: payment, search
- winner pays their own bid?
- yes, first price
- next bid must beat by how much?
- top plus the min increment
- reserve not met?
- no sale, seller is told
- can the seller bid?
- no
- bid at the end second?
- only if before the end time
- proxy bidding? as an extension
Entities
The entities. The auction house is the service that holds all auctions. An auction knows its item, its seller, its times and its price rules, and it tracks the top bid. A bid is who, how much and when. When an auction closes it produces an outcome: sold to someone at a price, reserve not met, or no bids. Listeners hear about new top bids and closing.
Class diagram
The types. Money is a long number of cents. A bid is an immutable record, and here is a neat trick: each bid holds a reference to the bid it beat. So the top bid is the head of a chain, and walking the previous links gives the full history in order. There is no separate list to keep in sync, which will matter a lot when we make bidding thread safe.
record Bid(String bidderId, long cents,
Instant at, Bid previous) {}
record Outcome(OutcomeType type,
String winnerId, long cents)
enum OutcomeType { SOLD,
RESERVE_NOT_MET, NO_BIDS }
history: follow previous to the start Lifecycle
The lifecycle. Before the start time an auction is scheduled. Between start and end it is live. Once the end time passes it accepts no bids, even if the closer has not run yet. When the closer runs, the auction becomes closed and its outcome is decided exactly once. Only closed is stored as a flag; everything else is computed from an injected clock, which also makes the tests fast.
- now before start: SCHEDULED
- start up to end: LIVE
- end reached, not closed: ENDED
- (no bids accepted)
- closer has run: CLOSED
- (outcome decided, once)
- time comes from an injected
- Supplier<Instant>
Bid rules
Put every bid rule in one method. Reject if the auction is closed or the end time has passed. Reject if it has not started. Reject the seller. Then compute the minimum: the starting price if there is no bid yet, otherwise the top bid plus the increment. Notice the reserve price is not checked here; a bid below the reserve is fine, it just will not win the item. The method returns a reason, or nothing when the bid is valid.
if (s.closed() || !now.isBefore(endAt))
return "auction has ended";
if (now.isBefore(startAt))
return "not started yet";
if (bidder.equals(sellerId))
return "sellers cannot bid";
long min = top == null ? startCents
: top.cents() + minIncrementCents;
if (cents < min) return "min is " + min;
return null; // valid Flow: place a bid
The bid flow. The bidder calls the auction house, which subscribes the bidder's inbox to that auction and passes the bid on. The auction reads its current snapshot, checks the rules against it, builds the new bid that points to the old top, and swaps the snapshot in. Only after the swap succeeds does it tell the listeners. Notifications never run while anything is locked.
Concurrency
Here is why the naive version breaks. Two bidders read the same top bid of one thousand. Both pass the check. One writes eleven hundred, the other writes ten fifty a moment later, and the top bid goes down. Both were told their bid was accepted. Under load this happens, and it is exactly the bug an interviewer is waiting for you to spot.
if (cents >= top + increment) {
// another thread runs here
top = new Bid(bidder, cents);
}
A reads 1,000, B reads 1,000
A writes 1,100, B writes 1,050
top is now LOWER than a
bid that was accepted Compare-and-set
The fix is compare-and-set on an immutable snapshot. The auction keeps one atomic reference to a small record holding the top bid and the closed flag. A bid reads the snapshot, validates against it, and tries to swap in a new one. If someone else swapped first, the swap fails and the loop runs again with fresh data, so the rules are always checked against the real top bid. No locks, and readers never wait.
while (true) {
State s = state.get();
String why = reject(s, bidder, cents);
if (why != null) return rejected(why);
Bid b = new Bid(bidder, cents, now,
s.top());
if (state.compareAndSet(s,
new State(b, false)))
{ notify(b); return accepted(); }
// lost the race: check again
} Close vs late bid
Why put the closed flag inside the snapshot? Picture the closer reading the top bid to pick a winner while a last bid slips in. With a separate flag, that bid could be accepted after the winner was chosen. Because closing is also a compare-and-set on the same snapshot, either the bid lands first and the closer sees it, or the close lands first and the bid's swap fails and it sees closed. There is no in-between.
Concurrency
Is a lock wrong? Not at all. Making place bid and close synchronized on the auction is simple and correct, and for most auctions it is plenty. Compare-and-set avoids waiting, and readers who only show the top bid never block. In a database the same idea is a conditional update that changes the top bid only if it is still the one you read and the auction is not closed. Say which you picked and why.
- synchronized placeBid + close:
- simplest, correct, fine for
- most auctions
- CAS on a snapshot:
- no waiting, readers never
- block, retries under a storm
- database: UPDATE .. SET top =
- ? WHERE id = ? AND top = old
- AND closed = false
Observer: alerts
Notifications use the Observer pattern. The auction keeps a copy-on-write list of listeners and, after every successful bid, calls on new top. Each bidder's inbox is subscribed the first time they bid. The inbox checks whether the bid that was just beaten was its own; if so, it records you were outbid. Email, push and a live price ticker are just more listeners, and the auction never changes.
interface AuctionListener {
default void onNewTop(Auction a, Bid top)
{}
default void onClosed(Auction a,
Outcome o) {}
}
Inbox: if top.previous() was me
and top is not me: "outbid"
listeners: CopyOnWriteArrayList Flow: closing
Closing. A timer calls close due every few seconds. It reads the clock once and closes every auction whose end time has passed. Close is a compare-and-set that flips the flag, so if two timers run at once, only one produces an outcome and the other gets nothing back. The outcome goes to all listeners. In the demo a fake clock jumps past the end time, so nothing sleeps.
Instant now = clock.get();
for (Auction a : auctions.values())
if (!now.isBefore(a.endAt))
a.close().ifPresent(o ->
results.add(a.id + " " + o));
close() returns empty if it was
already closed: runs once Reserve price
The reserve price is the lowest amount the seller will accept, and bidders do not see it. It is checked only once, when the auction closes. No bids means no sale. A top bid below the reserve means reserve not met, and the seller keeps the item. Otherwise the top bidder wins at their own bid. Keeping this in one small method makes the rule easy to change, for example to show a reserve met badge.
if (top == null)
return new Outcome(NO_BIDS, null, 0);
if (top.cents() < reserveCents)
return new Outcome(RESERVE_NOT_MET,
null, 0);
return new Outcome(SOLD,
top.bidderId(), top.cents()); Proxy bidding
Proxy bidding is the classic extension. A bidder says: bid for me, up to fifteen hundred. The neat part is that this needs no change to the auction at all. A proxy bidder is just another listener. Whenever someone else takes the top spot, it places the smallest valid bid on its owner's behalf, as long as that stays within the maximum. When the next bid would pass the maximum, it stops, and the owner's inbox says outbid.
Watch it run. Meera sets a maximum of fifteen hundred. Kabir bids thirteen hundred, and the proxy instantly answers thirteen fifty. Kabir bids fifteen hundred. The proxy would need fifteen fifty, which is above the maximum, so it stays quiet, and Meera's inbox gets an outbid alert. Real sites resolve two proxies in one step instead of bidding back and forth; mention that as a refinement.
record ProxyBidder(String userId,
long maxCents) implements
AuctionListener {
public void onNewTop(Auction a, Bid t) {
if (t.bidderId().equals(userId))
return;
long next = a.minimumNextBid(t);
if (next <= maxCents)
a.placeBid(userId, next);
}
} Concurrency
Check every shared thing. The top bid and the closed flag live together in one atomic snapshot, and because each bid links to the previous one, the history is inside that snapshot too, always consistent. Listeners are in a copy-on-write list, and watcher ids in a concurrent set. Auctions sit in a concurrent map. Notifications happen after the swap, and closing is a swap too, so it happens once.
- top bid + closed: one
- AtomicReference<State>
- bid history: immutable chain
- inside the snapshot
- listeners: CopyOnWriteArrayList
- watchers: concurrent key set
- auctions: ConcurrentHashMap
- notify after the CAS, never
- while holding anything
- close(): CAS, so it runs once
Extensibility
Interviewers like to add rules. Anti-sniping, where a bid in the last two minutes extends the auction, moves the end time into the snapshot so the same swap updates it. A buy-it-now price closes the auction on a matching bid. A Dutch auction, where the price falls over time, is a different auction type. To persist, store bids in a table with a unique auction and sequence number, so the database rejects a racing duplicate.
- anti-sniping: a late bid moves
- endAt forward (into State)
- buy-it-now price: a rule that
- closes on a matching bid
- Dutch auction: a new Auction
- type, price drops on a clock
- bid retraction: a new event
- persist: bids table, unique
- (auction_id, sequence)
Testing
The full code is below the player. The demo rejects a seller bidding on their own item and a bid below the increment, shows an outbid alert, runs a proxy bidder until its maximum, moves the fake clock past the end and rejects a late bid, then closes the auction as sold. A second auction ends with the reserve not met. Finally eight threads bid at once, and the top is always the biggest bid, with a strictly rising history.
sam bids on own item -> rejected meera 1,000 -> accepted kabir 1,020 -> min is 1,050.00 kabir 1,100 -> accepted, meera outbid meera proxy up to 1,500 kabir 1,300 -> proxy 1,350 ... kabir 1,500 -> proxy stops clock +61 min: late bid rejected A1 SOLD to kabir for 1,500.00 poster: RESERVE_NOT_MET race: top is the biggest bid
Follow-ups
Expect these follow-ups. Two bids of the same amount? The first swap wins and the second now fails the increment rule. Millions watching one auction? Publish new top bids to a message broker and fan them out to websockets. A server restart? Rebuild each auction's top from the bids table. Clock skew? One server's clock decides the end. And if the winner never pays, offer the item to the next highest bidder.
- two bids, same amount?
- first CAS wins, second fails
- millions watching one auction?
- push via a message broker
- server restarts mid-auction?
- rebuild from the bids table
- clock skew between servers?
- one time source decides
- winner never pays?
- offer to second highest
Say it like this
Here is the short version to say out loud. Each auction keeps one atomic snapshot holding the top bid and the closed flag. Bids are validated against it and swapped in with compare-and-set, and closing is also a swap, so no bid sneaks in after the winner is chosen. Inboxes and proxy bidders are listeners, and time comes from an injected clock.
- "An auction keeps one atomic
- snapshot: top bid and closed.
- Bids validate against it and
- swap it with compare-and-set;
- closing is a swap too, so no
- bid sneaks in after. Inboxes
- and proxy bidders are
- listeners. Time is injected."