29

If you imagine a company like Amazon (or any other large e-commerce web application), that is operating an online store at massive scale and only has limited quantity of physical items in its warehouses, how can they optimize this such that there is no single bottleneck? Of course, they must have a number of databases with replication, and many servers that are handling the load independently. However, if multiple users are being served by separate servers and both try to add the same item to their cart, for which there is only one remaining, there must be some "source of truth" for the quantity left for that item. Wouldn't this mean that at the very least, all users accessing product info for a single item must be querying the same database in serial?

I would like to understand how you can operate a store that large using distributed computing and not create a huge bottleneck on a single DB containing inventory information.

  • Amazon architecture in the mid-2000's (still relevant to your question): highscalability.com/amazon-architecture – Joeri Sebrechts Dec 12 '16 at 9:09
  • This also happens with seats in airplanes (or for e.g. packaged holidays where one item in the shopping cart represents a flight there, a rental car, a hotel stay and a flight back), with many different agencies selling the same seats on their respective sites. Solutions are myriad but they all come down to having one final truth database with the actual status for each part somewhere. – RemcoGerlich Dec 12 '16 at 9:50
  • 1
    @RemcoGerlich: the way you say "one final truth database" makes me think of a single machine with the big sacred database on it. In reality, what happens for critical data is rather that all the transactions reach multiple servers at once, ensuring that all those databases are in sync at all times. – Arseni Mourzenko Dec 12 '16 at 11:01
27

However, if multiple users are being served by separate servers and both try to add the same item to their cart, for which there is only one remaining, there must be some "source of truth" for the quantity left for that item.

Not really. This is not a problem that requires a 100% perfect technical solution, because both error cases have a business solution that is not very expensive:

  • If you incorrectly tell a user an item is sold out, you lose a sale. If you sell millions of items every day and this happens maybe once or twice a day, it gets lost in the noise.
  • If you accept an order and while processing it find that you've run out of the item, you just tell the customer so and give them the choice of waiting until you can restock, or cancelling the order. You have one slightly annoyed customer. Again not a huge problem when 99.99% of orders work fine.

In fact, I recently experienced the second case myself, so it's not hypothetical: that is what happens and how Amazon handles it.

It's a concept that applies often when you have problem that is theoretically very hard to solve (be it in terms of performance, optimization, or whatever): you can often live with a solution that works really well for most cases and accept that it sometimes fails, as long as you can detect and handle the failures when they occur.

  • 2
    Pat Helland's Memories, Guesses, and Apologies also covered in Building on Quicksand and compensating transactions are relevant ideas here. – Derek Elkins Dec 13 '16 at 3:47
  • 1
    You said "not really" but I feel like you're agreeing with what I suggested. It sounds like what you're saying is that when the user is just browsing, we give a cached approximation of the remaining inventory, but only when they actually try to complete the purchase do we do the write to decrement the remaining inventory. The DB containing that value will execute each transaction atomically, and if two users try at the same time, we show an error message for the second, since this is unlikely to happen. So, there eventually is one integer on a single machine that contains "the truth." – mattgmg1990 Dec 13 '16 at 5:46
  • 2
    @mattgmg1990: correct, eventually you of course have to know "the truth" somewhere, but the important difference is that the processing of orders can be done in a queue so you don't need concurrent atomic write access at all. In my case, the "error message" actually came hours after I finished the order on the Amazon website - I got an email saying that they had problems with the supply of that item and I could choose to cancel the order or do nothing and wait for them to fulfill it. I did the latter since I didn't need the item immediately, and they actually delivered it several weeks later. – Michael Borgwardt Dec 13 '16 at 8:29
  • @DerekElkins that's a great article, especially the point about digital data being a representation of reality that is unavoidably imperfect because reality can always have changes your system cannot automatically know about. – Michael Borgwardt Dec 13 '16 at 8:34
6

A combination of

  • hashing
  • sharding
  • replication
  • distribution
  • high fail-over
  • key-value stores

There's no magic, just more and more complex situations. Just like DNS, it is made to scale.

The 'single version of the truth' is part of such systems. Generating a new key becomes a more complex operation than just generating the next number in the sequence. For example other sequences exist. This is the sort of complexity that distributed database systems can handle and they do it by making several operation to and from components when making new objects, making them available to others, ensuring that sequences are unique when they need to be, composite keys, etc.

  • I've read about each of these concepts but the part I keep getting stuck on is the specific scenario of remaining inventory. If there's only 5 books left, and users making requests on multiple servers, do they always resolve to a single database table when it comes time to query the remaining inventory to ensure no two users can get the last book at the same time? What specific use of the above is making it so that this isn't slowing down the whole system and replication can still be useful with multiple DB instances? – mattgmg1990 Dec 12 '16 at 1:18
  • Added a bit more. i can't really explain all the complexity involved in this format, sorry. – Michael Durrant Dec 12 '16 at 1:30
  • 1
    Only some people are interested in the any given book, this means, book can be handled by a shard with relatively small load. – Basilevs Dec 12 '16 at 2:02
  • 6
    I think in the scenario you're describing the system just has to apologize to the user that someone else bought the last copy. I imagine this does occur from time to time. – Matthew James Briggs Dec 12 '16 at 8:55
  • 1
    I bet that there's only 5 books left indicator is less computing and more marketing. – mouviciel Dec 12 '16 at 8:57
5

I have seen the 'Last Item In Stock' problem solved in the following way:

Update all the stock levels daily and flag products as high, low, on order or out of stock categories according to threshold levels.

Obviously its the 'low stock' items which are problematic

  • Items with high stock levels

Don't bother checking the stock level. Just place the order

  • Items with low stock levels

Warn the user when browsing 'Last few left!'. when they go to pay, check and decrement the stock level. If its out of stock, Update the item status.

This way you only hit the database for the 'low stock' items and you only do that when the customer is quite far down the process of buying. The cost is that some customers will not be able to complete their purchase.

However, In most cases 'out of stock' really just means you are waiting for another delivery, so you want to accept the order anyway and maybe just pop up a warning or restrict the delivery options. So those customers arent lost.

During high load times such as sales, you might even turn the stock checking off and just email customers later, 'sorry we ran out of X, would you like Y'

Essentially the aim of any ecommerce platform is never read from the database. Always serve cached pages and do everything client side.

2

In this video, Martin Fowler discusses NoSQL databases:

https://www.youtube.com/watch?v=qI_g07C_Q5I

One of the points (somewhere in there), is that places like Amazon would rather keep 99% of people happy by accepting their order without being able to check "for sure" whether it's actually available, and maybe irritate a very small percentage by having to say "sorry, looks like someone beat you to it."

Which is to say, there's no real handling for the scenario you describe, just that Amazon takes the benefit of the doubt based on the last successful inventory read, and if a concurrent transaction slipped in between - oopsie.

(btw, that's a great video if you're curious about NoSQL)

Not the answer you're looking for? Browse other questions tagged or ask your own question.