How to avoid race condition in reservation system [duplicate]

Question

I'm trying to design a system to buy mangoes (not really mangoes, but it's a good proxy). One mango is the same as the other. These are very high-in-demand mangoes; quite possible many people at once will try to get a mango and there is a fixed amount of inventory.

Users will reserve a mango first, securing it for them to purchase and then if they don't buy it within 10 minutes, the reservation is cancelled and that mango can be purchased by someone else.

Here's where I see a race condition, and I am not sure how to best avoid it:

1. Customer requests to reserve a mango
2. Check inventory exists via inventory API (remaining inventory - reservations)
3. Sufficient inventory
4. Request reservation via reservation API. API starts to create reservation.
5. User 2 calls inventory API and finds there is enough mangoes left
6. User 2 calls reservation API. API starts to create reservation.
7. User 1 reservation is complete. They reserved the last mango
8. User 2 reservation is complete. They also reserved the last mango.

I really want to avoid this scenario: With both users having successfully reserved the last mango, user 2 buys the mango, leaving user 1 with an error message when they try to buy.

Oh and my mango system is distributed, so multiple different instances running.

I've searched up and down Google and surprisingly can't find an answer on preventing race conditions in inventory systems other than locking the DB. Is this really the best approach?

Answer 1

First: preventing race conditions in distributed systems is a really hard problem, don't be surprised when you don't find an easy solution.

Second, your scenario is unnecessarily complex and may be confusing you about the core of the problem: the act of reservation is basically the same as buying, which is basically the same as decrementing a counter.

So what you need is something like a distributed atomic counter. Search for this term, and you will find implementations as well as CS lectures on how to implement this.

Now pragmatically, the best way to implement this is almost certainly a central SQL DB with locking, because unless there are really tens of thousands of people buying those mangoes at the same time, an SQL DB on a fast server is still able to handle that if you take care to keep the transactions short, and it's much easier to find help, get the system as a whole right, and make it perform, than with any distributed solution.

Answer 2

Considering race conditions when designing algorithms is good. But there is a limit to perfection, in terms of acceptable quality here.

Oh and my mango system is distributed, so multiple different instances running.

This is a big, big stick in the wheels. Regardless of whether your writes are single-instance or distributed, when your reads are distributed you inherently breach the field of eventual consistency, which is going to make it really hard for you to 100% guarantee perfect information towards your end user at all times.

There is a wide variance to how tightly you want to control your race conditions and/or eventual consistency. While it might be nice to never have a customer mistakenly think something is in store when in fact it isn't, the cost, effort, and deployment scale needed to 100% guarantee this at all times, for all possible server loads, is probably too cost-prohibitive to be worth considering.

I've searched up and down Google and surprisingly can't find an answer on preventing race conditions in inventory systems other than locking the DB. Is this really the best approach?

In practical terms, a high-availability stock-trading app will be much more of a stickler for perfect information than a webshop for homemade candles, and the development/deployment cost and effort will exponentially increase because of it.

For that candle shop, a locked db is a fairly easy way of ensuring capping orders at the registered inventory, but it can be a bottleneck if the webshop is highly trafficked.
Comparatively, the stock-trading app may have a more distributed write system, but to ensure order capping to the same degree of certainty, it's going to be several orders of magnitude more complicated and expensive.

It's impossible for me to account for specifically the degree of race condition avoidance you need (relative to effort/cost of development), because it's so unclear where you draw the lines. However, you actually already have the answer yourself, you just havent found it.

This is precisely why the rest of this answer will be given in function of how you would've already developed your order logic, because the reservation logic can be reusably composed of existing order logic. Therefore, to whatever degree of security you already wanted your order processing to be, you can easily make the reservation processing to the same degree of race condition avoidance.

---

Here's an interesting way to think about a (seemingly unrelated) problem. Forget reservations. Think of a normal webshop. What does placing an order entail?

• An order is created
• Ordered goods are taken from the inventory
• Customer pays the order cost

Now think of making it possible to cancel orders freely. This is more commonly allowed in webshops where the purchased products need to be picked up by the customer, as opposed to being shipped to them.
What would the system need to do during such a cancellation?

• Close the order
• Return the order content back to the inventory
• Refund the customer

That sounds oddly like how you want your reservations to work, barring refunds since the customer didn't pay anything yet.

I'm not suggesting that you should merge reservations and orders in the same table (though it is technically viable, it's a dirty approach). However, even if stored in two different tables and functionally completely unrelated modules of your codebase, consider that both reservations and orders will use a very similar approach here.
However your placed orders would've decreased the stock inventory, the reservations can do the same thing, immediately effecting product availability.

Reservations, as you described them, are essentially non-paying orders that can be cancelled. When made, they immediately decrease the stock inventory (just like how yoiu would've implemented it for "real" orders), and additionally there's an automatic timer (10 minutes) that automatically cancels reservations of a certain age (from webshop building experience; you might consider implementing a similar deletion timer for orders that don't get paid).

The reason I'm mentioning this is because this means that however you would already have solved the race conditions for your orders, you can solve the reservation race condition the same way, because you can implement reservations as if they're cancellable orders.

As established above, there is a wide variance to how tightly you want to control your race conditions. While it might be nice to never have a customer mistakenly think something is in store when in fact it isn't, the cost, effort, and deployment scale needed to 100% guarantee that is probably too cost-prohibitive to be worth it.