Hacker News Reader

Comment by manbash | Hacker News Reader

> Instead of one row per item with a quantity column, we use one row per sellable unit. An item with 10 units has 10 rows.

> But one row per unit for all inventory would break down at scale—an item with 50,000 units across 10 locations would mean 500,000 rows, and the reserve query would slow as it scans through them. Instead, we maintain a bounded pool of available rows, capped at 1,000 per item/location combination. Reservations consume rows from this pool; a replenishment process refills it from the inventory ledger.

Shouldn't I feel uncomfortable with such approach? It seems to create a backoff (pool) for lowering the chance of having a synchronization issue.

View on HN

I agree, it does seem awfully complicated and there are quite a few pieces missing for this to be a complete solution.

I'm a bit surprised about the scalability case against a simpler solution. This is not about Shopify's scale. We're talking about contention for a specific SKU of a specific seller at a specific warehouse location.

How many shopping carts are competing for a single SKU at the payment stage at peak hours? Can this really be too much lock contention for a single database row?

I realise Shopify engineers are neither stupid nor inexperienced. Hence my surprise. I would have liked to hear more about that specific problem.

> Can this really be too much lock contention for a single database row?

When you consider how many other (often poorly-crafted) DB queries and service calls are being performed while holding the row locked, yes, it can rapidly add up. If the entire pipeline takes 500 msec, congratulations, you can’t sell more than 2 units per second of that SKU. If the item is popular and being actively hyped, then yes, that can be a problem.

Flash sales are a huge scaling issue for Shopify. There are celebrities who want to sell thousands of items in a few minutes window at the end of an advertised countdown.

Basically this is an incredibly rare case but a feature that they want to support.

There were woot offs 20 years ago. Flash sales are not some new scaling issue.

Its also not a solved one considering basically no platforms support them.

It's not? Shopify does it, woot does it, amazon does it, yes style does it, royal Caribbean does it.

Seems like a lot of places can do it for it not to be a solved problem.

Makes sense.

We observe 200+ (can’t say closer number) purchases per second for single SKU with good marketing and price.

The other thing that bothers me - why not real stable, but maybe „too old, medieval” solution with Redis as the main source of through - without any sync with SQL at all in terms of stock… it worked in my previous job with much higher traffic (1000s/s). Yup, we ended up with app-side sharding, but it was stupid-simple.

You need a sql DB for the actual purchase transaction, you can’t keep financial records in Redis.

As they say in TFA they used Redis for the cart reservation but then you need to sync the two stores.

Comes down to type of items, when you have physical inventory the number is limited so more manageable and interestingly enough the problem only applies to physical inventory.

You are just spending some more disk space to avoid synchronization issues. Denormalization for performance is a really common pattern, just that people do not start with it in the first place itself

I would call this one-row-per-contract-type, and this is the most general model for the problem (e.g. the model cannot be further broken down into finer level), thus, the most scalable model given storage is dirt cheap.

Storage might be cheap but search and RAM isn't

RAM may be expensive for a person, but still is quite cheap for the company.

Yeah, I'd be uncomfortable with that approach. One of their key design goals was to minimize underselling, recognizing that it results in lost revenue. But if a seller has 5k inventory in one location, has a spike of 2k orders, but only 1k of the orders can successfully reserve inventory, then isn't that an argument that you lost the revenue of the 2nd 1k orders that error out before the replenishment process succeeds?

I'm skeptical of this approach. Sure, row contention means that you cannot have a database transaction per customer order attempting to decrease inventory count by 1 each time. But you can have a batch transaction whereby the transaction decreases inventory by 100 (thus touching the high-contention inventory row once) and credits each of 100 different customer cart database rows (which are not under heavy contention and can be on a different disk entirely). Attempted customer orders are submitted to a reservation system put in charge of assembling the batches. Customers wait some short period of time - say, 15 seconds - for the reservation attempt to be batched and to be notified that they successfully locked a reservation. Arguing that "slow reservations trigger throttling and a worse buyer experience", without an actual number for what counts as "slow" to serve as an SLO and as a design target, is a cop-out inviting over-engineering.

> But if a seller has 5k inventory in one location, has a spike of 2k orders, but only 1k of the orders can successfully reserve inventory, then isn't that an argument that you lost the revenue of the 2nd 1k orders that error out before the replenishment process succeeds?

They explicitly cover this in the article, saying they do reservation inline. It does increase latency for these orders, but it doesn’t result in an error

> But you can have a batch transaction whereby the transaction decreases inventory by 100 (thus touching the high-contention inventory row once) and credits each of 100 different customer cart database rows (which are not under heavy contention and can be on a different disk entirely).

They mention this as well, checkout batching increased implementation complexity.

> Arguing that "slow reservations trigger throttling and a worse buyer experience", without an actual number for what counts as "slow" to serve as an SLO and as a design target, is a cop-out inviting over-engineering.

True. The article would’ve been better if they included such numbers. However the fact that they didn’t mention this doesn’t imply they haven’t done research. I haven’t found anything related to checkout specifically, however there are in general articles, indicating that increased latency correlates with revenue drop.

you should, their design is not the best. There is middle ground between "one row per SKU" and "1000 rows per SKU".

Its called one row per shopping cart*SKU combo.

if two people order 100 and 500 items of the same SKU, respectively, the table should have only two rows: for order1 and order2. Not 600 rows.

The problem is that in this case you have to do splits/merges. And while there are products that are sold by 100 units at a time, I think in most cases people by 1-2 items so the hassle might be not worth it.

Also you might not understand the original problem. Imagine if 100 customers want to buy product A. One thread starts a transaction, searches for amount of product A and UPDATE's it and goes searching for other products. The database locks the row until the end of transaction and other 99 treads cannot continue until first transaction commits (they can read but cannot update the rows).

This is why they made a row per item. In this case, transaction 1 hopefully locks only several rows with items of product A. Transaction 2 instead of waiting for lock release skips them (due to SKIP LOCK) and locks several next rows. And so on.

Obviously you do not need to make a row per item - if the available amount is really large (10 000 items), you could have for example 100 rows having 100 items each. In this case each transaction locks the whole row (100 items) even if it wants to reserve just one item. The problem though is that now every row might have different amount of available items and you have to do more work to reserve the amount you want.

ok, lets model situation of 100 customers and one last remaining item. Who will get the last item?

in shopify's design, it is a user who was the first to lock the row and have successful payment. Sounds good, but how often does it happen ? It's a rare and extreme case and they model their entire system after the rare even, and incur the overhead of 1000 rows per SKU per shop for all combination of SKU and shop_id for all the normal items that are not sold out in flash sale.

the same outcome could be achieved without locking and without creating 1000 rows:

  1. keep track of all active carts at the checkout in a table
  2. for each cart, record the timestamp in nanoseconds when user clicked Pay (but I would prefer timestamp of clicking Checkout)
  3. that timestamp will decide who gets the last available item.
  4. in a shopping cart, have explicit field for each SKU: inventory_reserved. 
  5. this decision mechanism is now explicit via global monotonic non-decreasing counter. It is no longer tied to payment processing gateway timeouts, not opaque and implicit mechanism relying on database internals and quirks of how DB engine locks and releases some placeholder rows.

On a large scale "rare" events happen every day. That is why people use locks and transactions or other measures.

In case with shopify, they want to decide whether the user may place order or not, at the moment when the user clicks "Pay" or some other button. If the user cannot place an order, they are shown the error, if they can, the items are reserved and the user is redirected to the payment page. So payment is processed only after successful reservation, and reservation is made only if the user wants to pay. The similar system works for buying train tickets online in my country, for example.

In you case, when user A clicks a button, following happens (as I understand):

1 the server increments the counter

2 the server calculates available amount as (amount_in_stock - amount reserved by carts with time < counter)

3 if the amount is large enough, the server updates the "time" field for user's cart thus reserving the item

Imagine that at step 2 the user A sees that there is one item left. However before user A does step 3, another user B might reserve the item (complete all 3 steps), and proceed to the payment. Then user A then completes step 3 and proceeds to the payment too. Now we end up with both user A and B paying for the last remaining item which doesn't solve the stated problem. Shopify's solution doesn't have such issues.

This is a classical TOCTTOU situation. There were exploits against Linux kernel based on similar issues.

shopify is wrapping their entire dance with locking and moving rows inside a transaction. if you wrap step 1-3 inside transaction you will get same atomicity guarantee

but again, my idea was:

  1) do not use throwaway placeholder rows to imitate a single item
  2) do not rely on db engine to decide which transaction gets committed first (which customer gets the last item)
  3) model queue explicitly by introducing counter field that sorts and prioritizes customers' orders and decides which order gets fulfilled and which customers gets the last item

No, using transactions won't change anything here.

> do not use throwaway placeholder rows to imitate a single item

The point of using multiple rows for one product is to distribute the locks.

Can you explain how that works? With the row-per-item I can see how you’d use locking primitives etc easily to deal with multiple concurrent shopping carts claiming available inventory.. but how does your solution solve contention? There’d need to be some “number of items in inventory” row, wouldn’t there be contention on that?

The point of one row per item is that thousands of concurrent shoppers don’t need to block each other as they can each claim as many free rows as they need for themselves?

One other advantage is item serial numbers. Or something else that makes an item that seems the same but actually be unique (perhaps the warehouse it’s in?)

explained below in https://news.ycombinator.com/item?id=49228432

> an item with 50,000 units across 10 locations would mean 500,000 rows

I don't get it, Wouldn't that still only be 50,000 rows, just divided across locations?

they're saying they started with the dumb thing,

    item1_location1

    item1_location2

    ...

    item2_location1

    item2_location2

every (item, location) combo gets its own row, and then they moved to the smarter thing.

I guess it depends on how the replenishment process works. Unless you're ordering over 1000 of an item, I doubt it would be a problem.

replenishment is an unnecessary cludge that only exists due to poor design. an "algorithmical smell" if you wish

Depends on the scale. Most companies don't approach the scale where this matters.

Maybe the example numbers are just bad - but now you expect your system to fall down if you scale from 10 to 100 locations?

"Number of locations" is an input so if the system has been designed to handle up to 10, and not 100, then yes I would absolutely expect it to fail with the higher value.

Developers (and everyone else really) need to think about systems, with the system taking inputs like "number of locations", and producing outputs like "available inventory", and when the input parameters change outside of the designed scope, without the system itself changing, then you should expect things to break.

I'm familiar with the reserved row approach (I use SELECT FOR UPDATE SKIP LOCKED) and yeah this replenishing idea terrifies me.

Reply on news.ycombinator.com