Inventory Reservation

Track: Data consistency. 6 stages. Languages: Go, Python, JavaScript, Rust.

Think about buying the last seat on a flight. When you click "buy", the seat is held just for you while you type in your payment details. If you finish in time, the seat is yours for good. If you take too long, the hold ends and the seat goes back to being available for someone else. Build a stock store that works the same way: it holds units for a customer, gives them back if the hold runs out of time, and never lets two customers end up with the same unit.

Build New(), AddStock(sku, qty) to add units of an item (its sku is just its name), Reserve(sku, qty, ttl) to hold some units for a customer for ttl time units, Confirm(reservationID) to turn a hold into a real, final sale, Release(reservationID) to give back a hold's units early, Expire(now) to return the units of every hold whose time ran out, and Available(sku) -> qty to check how many units of an item are free right now.

Example, reserve and confirm: add 10 units of item A. Reserve 3 of them for 100 time units, then confirm that reservation. Available("A") reads 7, both right after the reserve and after the confirm (confirming does not free up anything, it just makes the hold permanent).

Example, release: add 10 units of item A and reserve 3 of them. Instead of confirming, release that same reservation. The 3 units come back, so Available("A") reads 10 again. Releasing the same reservation a second time must do nothing. It must not hand back the same units twice.

Example, a hold running out of time: add 5 units of item A and reserve 3 of them with ttl = 5. Available("A") reads 2. Call Expire(10), which tells your store that 10 time units have now passed. 10 is past the hold's 5-unit deadline, so its 3 units come back on their own, and Available("A") reads 5 again. Confirming that same reservation after it has expired must fail, it is too late.

Where a hold's deadline starts: Reserve has no now of its own. Use the last now your store was given by Expire (0 before the first call) and add ttl. So after Expire(10), a hold with ttl = 5 ends at 15: Expire(14) keeps it and Expire(15) gives its units back.

Time here is never read from a real clock. Every call that needs it gives you now yourself, a plain number that only goes up. Your code just compares the numbers you are given.

Many buyers at once: say only 1 unit of an item is left, and 5 different buyers all call Reserve for it at the exact same moment. Exactly one of them must succeed, never more. If your code checks how many units are free and then takes the units as two separate steps, two buyers can both see "1 is free" before either one has updated that number, and both would succeed, selling the same unit twice. Your Reserve must check the stock and take it in one single step that nothing else can get in the middle of, no matter how many buyers call it at the same time.

Implement New(), AddStock(sku, qty), Reserve(sku, qty, ttl) -> (reservationID, ok) (ok is false when there is not enough free), Confirm(reservationID) -> ok, Release(reservationID) -> ok, Expire(now), and Available(sku) -> qty, using your language's own names. Standard library only. Your code will be called from many callers at once, so it must be safe for that. For help with the ideas, read the notes. New to code that many callers run at the same time? Read Many callers at once first.

In JavaScript, only one piece of your code runs at a time, so a check and a take with no await between them can never be split. A real Node.js server keeps its data in a database, and that is where the race happens. So in JavaScript, New(db) gets a store from the tester, and you keep all your data in it with await db.get(key) and await db.set(key, value). Every method is async. Values are copied as JSON, like in a real database. While one call waits at an await, other calls run. If reserve reads the free count, waits, and then writes it back, another reserve can read the same old count in between, and both take the same units. In the stages that send one call at a time, the tester runs two copies of your code that share one db and sends the calls to them in turn, like two servers. Data kept only in a local variable or Map is not seen by the other copy, so it gives wrong answers.

Where it is used

Without a single step that checks and takes the stock, two buyers can both get the last unit, and the shop has to cancel one of the orders.

Stages

iv1: hello, add stock, reserve, and confirm (very easy)

Add 10 units of item A. Reserve 3 of them, then confirm that reservation. Check how many units are left. Example: AddStock("A", 10), Reserve("A", 3, 100) -> succeeds, Confirm(...) -> succeeds, Available("A") -> 7.

The tester will verify: the reserve succeeds, the confirm succeeds, and Available reports 7.

iv2: reject when stock is short, and return it on release (easy)

Add 5 units of item A. Reserve 3 (succeeds, 2 left). Reserve 3 more (only 2 are free, so it must be rejected). Release the first reservation twice: the first release must return its 3 units, the second release must do nothing. Example: after both releases, Available("A") -> 5, not more.

The tester will verify: the over-large reserve is rejected, the first release returns the units, and the repeat release does not add them again.

iv3: a hold that runs out of time gives back its stock (medium)

Add 5 units of item A. Reserve 3 with ttl = 5 (Available drops to 2). Call Expire(10), past the hold's deadline, so its units return on their own (Available goes back to 5). Confirming that same reservation after it expired must fail.

The tester will verify: availability reads 2 right after the reserve, 5 right after the hold's time runs out, and confirming the expired hold is rejected.

iv4: many buyers reserve the last units at once (hard)

Only 5 units of item A are left. 16 buyers all call Reserve for 1 unit each at the exact same moment. Exactly 5 of them must succeed, every single time this runs, no matter which 5. A second test follows. It runs 100 rounds (20 in JavaScript), and each round starts with 1,000 units of A. 8 buyers start together, and each one keeps reserving 1 unit until Reserve says no. Exactly 1,000 reservations must succeed in each round. In Go, Python and Rust the buyers run on real threads. In JavaScript they are async calls that overlap at every await on the db. Either way, a Reserve that checks the stock and takes it in two separate steps, or that uses no lock at all, gets caught here.

The tester will verify: exactly 5 of the 16 reserve calls succeed, and availability lands at exactly 0, not less and not more. Every one of the rounds also ends with exactly 1,000 successful reservations and 0 units left.

iv5: a long run of reserves, confirms, releases, and checks (hard)

A long run of 120 mixed calls (reserve, confirm, release, letting time pass, and checking availability) over two items, A and B. Every single answer along the way must match our solution exactly.

The tester will verify: all 120 answers, in order, match our solution's answers exactly.

iv6: make reserve and release fast (L2, hard)

Keep Reserve and Release fast, without scanning every hold you have ever made. Every answer must still stay correct. In JavaScript the db answers at once in this stage, but every call still copies its value, so keep each value small. Example: if our solution takes 100 ms, the limit is 150 ms. Your solution takes 140 ms, so it passes.

The tester will verify: your code takes at most 1.5 times as long as our solution in the same language and returns correct answers.

Rules

Read the Inventory Reservation notes in the wiki